単語の辞書 {'cat', 'cot', 'catalyst'} と、文字類似関係 f(x, y) があるとします。
f(x, y) = 1, if x and y are similar
= 0, otherwise
これらの「類似性」は、プログラマーが指定できます。そのように、たとえば、
f('t', 'l') = 1
f('a', 'o') = 1
f('f', 't') = 1
しかし、
f('a', 'z') = 0
etc.
クエリ「cofatyst」がある場合、アルゴリズムは次の一致を報告する必要があります。
('cot', 0)
('cat', 0)
('catalyst', 0)
ここで、数字は見つかった一致の 0 ベースの開始インデックスです。私はAho-Corasick アルゴリズムを試してみましたが、完全一致にはうまく機能しますが、キャラクターの「類似」キャラクターの数が比較的少ない場合、キャラクターの類似キャラクターの数を増やすと、そのパフォーマンスは指数関数的に低下します。誰かがこれを行うためのより良い方法を教えてもらえますか? あいまいさは絶対に必要であり、文字の類似性を考慮に入れる必要があります (つまり、編集距離だけにやみくもに依存しないでください)。