[B! levenshtein] gayouのブックマーク

【PHP関数】レーベンシュタイン距離を求める関数の日本語対応

■レーベンシュタイン距離とはこのコピペチェックツールで利用しているアルゴリズムです。編集距離とも呼ばれています。2つの文字列を何回変更すると同じ文字列になるかを求めるアルゴリズムです。レーベンシュタイン距離は数値が小さいほど同じような文字列であると判断できます。レーベンシュタイン距離が0のものが全く同じ文字列となります。このレーベンシュタイン距離ですが、phpではlevenshteinメソッドとして提供されています。しかし、このlevenshteinメソッドは2バイト文字列である日本語には対応していません。正しいレーベンシュタイン距離が出ません。今回は、この関数を２バイト文字列に対応させます。 ■2バイト文字に対応させる Qiitaで２バイト対応させるコードが公開されていました。ありがとうございます。この関数を利用することで、日本語でも正確にレーベンシュタイン距離を取得することが

gayou 2018/07/16

リンク

MySQLで編集距離を求めるUDF - CreateField Blog

先日、Groongaでビットパラレルで高速な編集距離の実装を検証してました。ビットパラレルを使ってGroongaで高速な編集距離関数の検証 - CreateField Blog 編集距離とは挿入、置換、削除、並び替えの編集操作によって一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数です。ちょこっとだけ表記ゆれしている文字列を抽出したりできます。ちょっとMySQLでもカジュアルに使いたいなぁと思って編集距離を求めるUDFをさくっと作りました。 naoa/mysql-edit-distance · GitHub １バイト文字であればビットパラレル法でそこそこ高速に編集距離を求めることができます。 10万レコードの比較文字数x文字数動的計画法ビットパラレル固定長 62x62 11.6524 sec 0.1811 sec とりあえず、英語で使いたかっただけということもあ

gayou 2018/07/16

リンク

How to add levenshtein function in mysql?

gayou 2018/07/16

リンク

SymSpell対BK木：100倍速い文字列のあいまい検索とスペルチェック | POSTD

注釈：500,000単語収録の辞書内における1,000単語の検索時間 X:最大編集距離 Y:検索時間/ms 従来、スペル修正や文字列のあいまい検索には、 BK木が適していると言われてきました。しかし、これは本当でしょうか。また、スペル修正に関する私のブログに寄せられたコメントには、BK木が、あいまい検索のためのデータ構造として優れていると言及されていました。そのような経緯から、今回、BK木と他の選択肢のベンチマークを取って比較してみようと思い立ったわけです。近似文字列検索アルゴリズム近似文字列検索では、文字列リスト内の文字列を検索し、特定の文字列メトリックに従って、それに近い文字列を返します。文字列メトリックは多数あり、例えばレーベンシュタイン距離、 Damerau-Levenshtein距離、ハミング距離、ジャロ・ウィンクラー距離、 Strike a m