✅1文字長の文字列をdeno-asearchで比較できない
発生した実装
現象
検索文字列と候補文字列の長さが共に1のとき、どのあいまい度でも検索に失敗してしまう
どちらかの文字列をより長くすれば回避される
原因
てっきり距離$ dでマッチした文字列は距離$ d+n\ (n>0)でもマッチすると思い込んでいた
実際にはちょうど距離$ dでマッチした文字列しか表示しないので、近い距離でマッチしても遠い距離でマッチしないことがある
それが一文字同士の比較だった
code:state
00 00
00 --> 01
00 11
10 01
1列目:初期状態
2列目:受理状態
受理状態ビットは01なので、距離0,1,2にはマッチするが距離3にはマッチしない
原因となるアルゴリズムは状態遷移機械ではなく受理判定の部分だから
対策
match()の判定方法を以下のように書き換える
1. 全てのレジスタと受理状態ビットとを比較して一致するかどうかを確かめる
大抵は近い距離より遠い距離でマッチするので、遠い距離から判定していけばいい
2. 「距離aでマッチした && 距離a-1でマッチしなかった」ら、距離aでマッチしたと判定を下す
2022-02-11 12:32:14 普通に距離が小さいほうから判定すればよくない?
最大4回の判定で終わる
何よりアルゴリズムが単純になる
逆に遅くなるだろ
一文字比較の単体テストを加える
2022-01-23
16:37:03 空文字マッチ失敗の修正も一緒に入れてしまった
16:32:53 pushした
あ、commit名ミスってた……
まあいいか
15:59:13 test()のほうも修正すべき?
引数に与えた距離とちょうど一致するかどうかを判定するならこれでもいいけど
引数名がmaxDistanceだから、それはまずいか
15:55:53 修正終了
pushはしていない
テストケースも加えた
空文字マッチに失敗することがついでにわかった
それも修正した