Myersのbit-parallel法で順不同にAND検索したい

動機

選択範囲に似ているリンクを入力補完するUserScriptではB.に近い方法で検索しているが、アルゴリズムをミスっていて、順不同検索がうまくいっていない

より正確に順不同検索する方法を探したい

候補

❌A. 検索語句のすべての重複順列で検索する

word1 word2 というように空白区切りでつなげた被検索文字列で検索する

利点

実装が楽

すべての検索語句の組み合わせに対して検索を実行すればいいだけ

欠点

順不同検索を3語程度までに制限する必要がある

組み合わせ爆発を回避するため

スペース区切りで3語まで順不同検索できれば、実用上は問題ないと思われる

実際、リンク入力補完 (scrapbox)は3語までしか順不同検索に対応していない

語句ごとに最大編集距離を設定できない

例えば scrapbox 補完 で最大編集距離が2以下の文字列を検索すると、 scrapbox に部分完全一致する文字列が全て引っかかってしまう

補完 が2文字なので、全て無視されてしまう

無理だこれ

Myersのbit-parallel法は .* 相当のワイルドカードマッチを実装できない

B. 一致箇所を記したリストから、各語句全てが重複せずに検索文字列に部分一致する組み合わせを探し出す

利点

検索回数を語句の数と同数にまで抑えられる

組み合わせ爆発が起きない

語句ごとに最大編集距離を設定できる

欠点

重複しないマッチ箇所の計算が重すぎる

各語句で一致したすべての箇所の組み合わせをチェックする必要がある

例えば wordA , wordB , wordC で検索して、それぞれ5箇所マッチした場合、最悪5^3=125回判定を行う必要がある

検索回数を抑えた効果が打ち消されてしまう

正確に一致箇所の組み合わせを計算できない

例えば wordA に編集距離1でマッチした場合、マッチした被検索文字列の部分文字列は wordB かもしれないし worddA かもしれないし wrdA かもしれない

wordB なら検索語句と文字数が同じなので、マッチの終了位置を正確に把握できる

他二つはそれが出来ない

この場合、実際にはマッチしているのにしていないと判断してしまうことがある

例えば wordA wordB は aaawrdAwordBbbb に編集距離1でマッチする

しかしマッチ終了位置=マッチ開始位置+検索語句の長さとしてしまうと、 wordA は wrdAw にマッチすると判定されてしまう

すると wordB は wordA のマッチ領域と干渉してしまうため、 wordB に完全一致できなくなる

今回の場合は wordB も編集距離1ならマッチできるが、完全一致しか認められなかったら aaawrdAwordBbbb を検索結果から取りこぼしてしまうことになる

この欠点は2023-03-07時点の実装にもあることだから、目をつぶっていい

3語句まで順不同検索して、4語以上は順序固定で検索すればいいだろう

#2023-03-07 20:45:35

#2023-02-12 07:17:53