Groongaのパトリシアトライを使って高速なあいまい検索を実装した - CreateField Blog

はじめに あいまい検索はたとえば、編集距離を求めることによって実現することができます。 レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される。 レーベンシュタイン距離 - Wikipedia 最もベーシックな動的計画法によって編集距離を求める場合、計算量はO(nm)であり、レコード郡から編集距離が近いものだけを列挙する場合、さらにレコード数分の比較が必要になり計算量がとても大きくなってしまいます。 文字列の比較自体は、ビット演算を用いることによりそこそこ高速化できますが*1、この場合

[tuto0621]

色々調べていると、トライの構造を利用することにより、結構簡単に演算量を抑えられることがわかりました