generated at
Bitap algorithmで使う最大Levenstein距離を検索文字列長から算出する計算式の検討
こんなのを考えている
list
文字列長編集距離
10
20
31
41
52
62
72
82
93
103
113
123
133
143
154
164
174
184
194
204
214
224
234
244
ある最大編集距離を使う文字列長の範囲を、2,2,4,6,10,16,26,\cdotsのようにFibonacci数列と同じ増加速度で増やしていく
実際には26の途中までしか使わない
Bitap algorithmの制約で、64bitマシンでは検索文字列長が64文字に制限されている
編集距離は6まで計算できれば十分

立式
文字列長が有限なので、各文字列長に対して編集距離を決め打ちで返しても問題ない
でもできることなら四則演算と丸め込みだけで求めたいところ
漸化式
x: 編集距離からそれを適用する文字列長の範囲の要素数を返す函数
x(0)=2
x(1)=2
x(n+2)=x(n)+x(n+1)
解
\alpha+\beta=1\land\alpha\beta=-1とすると、
x(n+2)-\alpha x(n+1)=\beta(x(n+1)-\alpha x(n))
x(n+2)-\beta x(n+1)=\alpha(x(n+1)-\beta x(n))
一般項は
x(n+2)-\alpha x(x+1)=\beta^{n+1}(x(1)-\alpha x(0))=2\beta^{n+1}(1-\alpha)=2\beta^{n+2}
x(n+2)-\beta x(x+1)=\alpha^{n+1}(x(1)-\beta x(0))=2\alpha^{n+1}(1-\beta)=2\alpha^{n+2}
\implies\begin{pmatrix}1&-\alpha\\1&-\beta\end{pmatrix}\begin{pmatrix}x(n+2)\\x(n+1)\end{pmatrix}=2\begin{pmatrix}\beta^{n+2}\\\alpha^{n+2}\end{pmatrix}
\iff\begin{pmatrix}x(n+2)\\x(n+1)\end{pmatrix}=2\frac1{\alpha-\beta}\begin{pmatrix}-\beta&\alpha\\-1&1\end{pmatrix}\begin{pmatrix}\beta^{n+2}\\\alpha^{n+2}\end{pmatrix}
\iff x(n)=2\frac{\alpha^{n+1}-\beta^{n+1}}{\alpha-\beta}
編集距離nからそれが適用される最大文字列長を求める函数l(n)を求める
l(n)=\sum_{i=0}^{i=n} x(k)
ここで、a(n+1)-a(n)=\alpha^{n}\iff a=\frac1{\alpha-1}\alpha^nより、
\frac{2}{\alpha-\beta}\Delta\left(\frac{\alpha^{n+1}}{\alpha-1}-\frac{\beta^{n+1}}{\beta-1}\right)=x(n)
\therefore l(n)=\frac{2}{\alpha-\beta}\left(\frac{\alpha^{n+2}}{\alpha-1}-\frac{\beta^{n+2}}{\beta-1}-\frac{\alpha}{\alpha-1}+\frac{\beta}{\beta-1}\right)
=\frac{2}{\alpha-\beta}\left(\frac{\alpha^{n+2}}{\alpha-1}-\frac{\beta^{n+2}}{\beta-1}\right)+\frac{2}{(\alpha-1)(\beta-1)}
\alpha-1=-\beta, (\alpha-1)(\beta-1)=\alpha\beta-(\alpha+\beta)+1=-1, \alpha^2(\beta-1)=-\alpha^3より
=\frac{-2}{\alpha-\beta}\left(-\alpha^{n+3}+\beta^{n+3}\right)-2
=\frac{2\left(\alpha^{n+3}-\beta^{n+3}\right)}{\alpha-\beta}-2
これの逆函数l^{-1}(L)が、検索文字列長から対応する編集距離を求める函数となる
......これを愚直に計算させるより、決め打ちで値の対応表用意したほうがずっと速いよな


#2022-05-15 09:16:34