boscono https://blog.hatena.ne.jp/boscono/ てきとうなメモ https://boscono.hatenablog.com/ Search NLP SimString どうやって高速化しているのか気になったのでメモ。基本的には辞書となるキーワードリストに対して、n-gram→キーワードのID(SID)のリストのマッピングをCDB(Constant Database)に保存しておいて、そこから入力文字列のn-gramを含むSIDがいくつn-gramを含むか数えていき、コサインやジャッカード係数などの尺度でn-gramの類似度が閾値を超える数になったものを類似文字列として出力するという考え方。高速化の方法としては2つ考えられている。1つは文字列の長さごとに別のCDBファイルにしてあるという部分。閾値と尺度と入力文字列の長さが決まると類似文字列… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fboscono.hatenablog.com%2Fentry%2F20110310%2Fp1" title=" SimStringメモ - てきとうなメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2011-03-10 00:00:00 rich https://boscono.hatenablog.com/entry/20110310/p1 1.0 100%