Luceneでレーベンシュタイン距離を求める - CLOVER🍀
先日、Apache Solrを使った「もしかして検索」や単語のサジェストみたいなところを調べていて、「レーベンシュタイン距離」なるものがあることを知りました。 レーベンシュタイン距離 - Wikipedia このあたりも参考になりました。 編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー スペルミス修正プログラムを作ろう また、Luceneで行った場合のエントリも。 2つの文字列間の距離計算の抽象化（スペルチェック）（2.4） | 関口宏司のLuceneブログ SolrのSuggesterを試してみる Wikipediaによれば、レーベンシュタイン距離は2つの文字列がどの程度異なっているかを示す距離で（編集距離）、文字列を何回の手順でもう片方の文字列とするように変形できるか、という感じみたいです。 同じく、Wikipediaのまんまですが、「kitt
キーフレーズ抽出ツール KEA を Lucene 上で実装する | 関口宏司のLuceneブログ
一定期間更新がないため広告を表示しています
Luceneで使われてるFSTを実装してみた（正規表現マッチ：VMアプローチへの招待） - Qiita
入力と出力のペアに対して，上のようなグラフを作るのが目標です．テーブルの出力のとこは数字が書いてありますが，文字列だと思ってとらえて下さい．map だと出力は1つに限られちゃいますが，ひとつの入力に対して出力が複数あってもいいです．たとえば入力 "feb" に対して，出力は "28" と "29" があります．（2月は28日と29日のときがありますね）． ノードの部分が状態で，そこから出ている矢印が状態遷移になります．矢印には a/b というラベルがついていますが，a の部分が入力とのマッチを意味し，b の部分がそのときの出力を意味します． 上の例で示すFSTで，"aug"を処理するには，"aug"を頭から読んで，入力"a"に対応するの(9)から(3)への矢印を選択します．そのとき，出力として"3"を記録しておきます．そのあと，"u"に対して(3)から(2)への矢印を選択し，"1"を先ほど
Luceneの曖昧検索を100倍高速化したアルゴリズム - nokunoの日記
@nobu_k さんのつぶやきでこのエントリを知りました。Changing Bits: Lucene’s FuzzyQuery is 100 times faster in 4.0Luceneで曖昧検索を効率化した話です。 最初の実装では、転置インデックスを全探索して編集距離がN以下の単語を拾っていたレーベンシュタインオートマトンという、編集距離がN以下の単語のみをアクセプトするオートマトンを利用することにした 単語ごとに構築したレーベンシュタインオートマトンをマージするという操作が必要になるが、なかなかうまくいかなかった 難解な論文を見つけたが、実装は難しかった良いライブラリを見つけたので、PythonからJavaに移植した 最後に1つだけ残ったバグは、移植の失敗ではなく元ライブラリのバグだった。報告すると1日で直ってきた。この前のエントリでは、有限状態トランスデューサを使った辞書の圧縮
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
