Myersのbit-parallel法による順不同AND検索のalgorithm検討
動機
候補
word1 word2 というように空白区切りでつなげた被検索文字列で検索する
利点
実装が楽
すべての検索語句の組み合わせに対して検索を実行すればいいだけ
欠点
順不同検索を3語程度までに制限する必要がある
スペース区切りで3語まで順不同検索できれば、実用上は問題ないと思われる 語句ごとに最大編集距離を設定できない
例えば scrapbox 補完 で最大編集距離が2以下の文字列を検索すると、 scrapbox に部分完全一致する文字列が全て引っかかってしまう 補完が2文字なので、全て無視されてしまう
無理だこれtakker.icon
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時点の実装にもあることだから、目をつぶっていいtakker.icon
3語句まで順不同検索して、4語以上は順序固定で検索すればいいだろう