Trigram という gem を作りました - milk1000cc
2 つの文字列の類似度を計算する Trigram という gem を作りました。 https://github.com/milk1000cc/trigram Trigram.compare 'he is genius', 'he is genius' # => 1 Trigram.compare 'he is genius', 'he is very genius' # => 0.5625 Trigram.compare 'he is genius', 'she is cute' # => 0.26666666666666666 Trigram.compare 'he is genius', 'I can fly' # => 0 文字列を 3 文字ずつに分割して、重複率を出す感じです。 以下の記事を読んでもらうと、よくわかると思います。 livedoor Techブログ : String:
Luceneの曖昧検索を100倍高速化したアルゴリズム - nokunoの日記
@nobu_k さんのつぶやきでこのエントリを知りました。Changing Bits: Lucene’s FuzzyQuery is 100 times faster in 4.0Luceneで曖昧検索を効率化した話です。 最初の実装では、転置インデックスを全探索して編集距離がN以下の単語を拾っていたレーベンシュタインオートマトンという、編集距離がN以下の単語のみをアクセプトするオートマトンを利用することにした 単語ごとに構築したレーベンシュタインオートマトンをマージするという操作が必要になるが、なかなかうまくいかなかった 難解な論文を見つけたが、実装は難しかった良いライブラリを見つけたので、PythonからJavaに移植した 最後に1つだけ残ったバグは、移植の失敗ではなく元ライブラリのバグだった。報告すると1日で直ってきた。この前のエントリでは、有限状態トランスデューサを使った辞書の圧縮
livedoor Developers Blog:String::Trigram でテキストの類似度を測る - livedoor Blog（ブログ）
こんにちは。検索グループ解析チームの nabokov7 です。 今回は、livedoor キーワードでの事例より、テキストの類似度を測るのに便利な手法を紹介します。 livedoor キーワードは、livedoor ブログでその日その日で話題になった語をランキング表示するサービスです。 当初、はてなキーワードやWikipediaを足して2で割ったようなサービスを作れといった開き直った指示のもとで開発が開始されたともいう、分社化前の芸風の名残で、キーワードの検索結果にはユーザが自由に解説を書き込める Wikipedia 的スペースもついています。 で、この解説部分に、さまざまなサイトから文章をまる写ししちゃう人がとても多いのですね。 特に多いウィキペディア日本語版からの剽窃を防止するために、livedoor キーワードでは以下のような対策を講じることにしました。 ウィキペディア日本語版の解説
Lucene's FuzzyQuery is 100 times faster in 4.0
There are many exciting improvements in Lucene's eventual 4.0 (trunk) release, but the awesome speedup to FuzzyQuery really stands out, not only from its incredible gains but also because of the amazing behind-the-scenes story of how it all came to be. FuzzyQuery matches terms "close" to a specified base term: you specify an allowed maximum edit distance, and any terms within that edit distance fr
開発メモ: 編集距離による曖昧検索
英和辞書の曖昧検索を実装したという話。それにあたってDB層で編集距離による絞り込みを実装している。 image:1:1331519319-spelling.png 曖昧検索 二つの文字列があったとして、一方をもう一方と一致させるために何回の編集操作が必要かという尺度を編集距離といい、それは二つの文字列の類似性を測るのに利用することができる。最も典型的なのはレーベンシュタイン距離である。 スペルミスをしてしまった場合に最も似た候補を出力してくれると英和辞書の機能としては嬉しい。というか俺はスペルミスをしまくるので俺にとっては必須の機能である。入力されたクエリから数文字分ずれていても検索できる曖昧検索機能が欲しいということだ。EngHelperの辞書機能にもそれを搭載しておきたい。 LとRの区別がつかない日本人としては、「english」を探そうとして「engrish」とか入力しがちである。そ
Javascriptでレーベンシュタイン距離の実演
Javascriptでレーベンシュタイン距離の実演 レーベンシュタイン距離は、2つの文字列の間にどの程度の差があるかを算出します。 具体的には、2つの文字を同一にするには、挿入・置換・削除を何回行えば良いか最小回数を算出します。 ※IE8、FF3.6、Chrome4で動作を確認しています。IE7以下では動作しません。 ※このスクリプトはイメージです。ほとんどテストしてないのでバグってたらすいません。 サンプル テキストボックスに文字列を入力してボタンを押すと、2つの文字列の距離が出力されます。
レーベンシュタイン距離を使って電話でのイライラを解決する - kenmazの日記
電話で自分の苗字を伝えようとしても、電話相手に正しく伝わらないことがある。私が「松前です」と告げても、電話相手は「はい、増前さまですね」と間違って復唱しやがることがある。いずれ「夏前」とか「安前」とか「松苗」とか、いろいろ間違われるようになるかもしれない。このような不運な事故を回避するには、事前に間違えられやすい苗字を洗い出しておいて、ばっちり発音を練習しておく必要がある。 さて「松前」と似ている苗字を洗い出すにはどうすればよいだろうか。そんなとき使えそうなのが「レーベンシュタイン距離」である。 「レーベンシュタイン距離」とは、ある単語を、別の単語に書き換えるために必要な、文字の挿入／削除／置換操作の回数のことである。レーベンシュタイン距離を使えば、ある単語同士がどれくらい似ているか、ということが分かる。 レーベンシュタイン距離 http://ja.wikipedia.org/wiki/%
PHP: levenshtein - Manual
levenshtein( string $string1, string $string2, int $insertion_cost = 1, int $replacement_cost = 1, int $deletion_cost = 1 ): int レーベンシュタイン距離は、string1 を string2 に変換するために置換、挿入、削除 しなければならない最小の文字数として定義されます。アルゴリズムの計算量は、 O(m*n) です。 ここで、n および m はそれぞれ string1 および string2 の長さです。 O(max(n,m)**3) となる similar_text() よりは良いですが、 まだかなりの計算量です)。 insertion_cost, replacement_cost かつ/または deletion_cost が 1 以外の場合、 変換コストが
文字列の類似度を測る(3) レーベンシュタイン距離の拡張｜Colorless Green Ideas
文字列の類似度を測る単純な尺度としてレーベンシュタイン距離というものがあるが、このレーベンシュタイン距離を拡張した様々な指標について見ていく。 はじめに 以前、文字列の類似度を測る手法として、レーベンシュタイン距離というものを紹介した。これは、ある文字列から別の文字列にする際に挿入・削除・置換を何回行うかに基づいて、文字列の類似度を測る尺度であった。レーベンシュタイン距離は簡便な指標であり、実際色々な分野で使われている。ただ、レーベンシュタイン距離だけでは捉えきれない問題もあって、そういう場合は、レーベンシュタイン距離以外の方法で文字列の類似度を測ることになる。 今回は、文字列の類似度を測るための尺度の中でも、レーベンシュタイン距離を拡張したものについて紹介していきたい。特に、Damerau–Levenshtein距離というものと、距離の標準化の話は重要になってくるので、おさえておくと何か
文字列の類似度を測る(1) レーベンシュタイン距離｜Colorless Green Ideas
ある文字列と別の文字列の類似度を測る手法の1つである、レーベンシュタイン距離について紹介する。文字列の類似度は検索エンジンやDNAの塩基配列の調査などにも使用されており、応用範囲は広い。 はじめに Googleの検索結果の訂正候補 検索サイトで検索語を間違えて入力してしまった場合、検索エンジンが訂正候補を出してくれることがある。図に掲げた例では、「マクドナルド」と入力しようとして、誤って「マクラナルド」と入力してしまっているが、Google は「マクドナルド」の検索結果を返している。誤ったものを入力すると、その誤ったものと似た正しいものを返しているのである。 このように訂正候補を出すには、まず入力されたものと似ているものを探し出すということが必要になる [1] 。そして、似ているものを探し出すには、何をもって似ているとするのかということを決めなくてはならない。つまり、類似度の尺度が必要とな
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Rails fuzzy searching with Sunspot gem