いきなり答える備忘録

Google Workspace(旧G Suite)・Microsoft 365・LibreOfficeなどに関するメモ

(Excel)レーベンシュタイン距離を求める

 Excelのワークシート関数で、2つの文字列の違いの度合いを測るレーベンシュタイン距離(編集距離)を求める例です。
 1セル内の式で完結し、2つの文字列の距離のみを求める内容としています。

  • REDUCE/LAMBDA関数等を利用してレーベンシュタイン距離を求めることができます。

手順

 画像ではD3セルに式を入力し、B3,C3セルに記録されている2つの文字列のレーベンシュタイン距離を求めています。

 D3セル

=CHOOSECOLS(
LET(a,SEQUENCE(1,LEN(B3)+1,0),b,SEQUENCE(LEN(C3)),c,SEQUENCE(LEN(B3)),
REDUCE(a,b,LAMBDA(a,b,
REDUCE(b,c,LAMBDA(b,c,
HSTACK(b,MIN(INDEX(a,c)+(MID(B3,c,1)<>MID(C3,INDEX(b,1),1)),INDEX(a,c+1)+1,INDEX(b,c)+1))
))))),
-1)

 いわゆる動的計画法(DP)に基づく式となっています。
 この方法に関しては式を各セルに分散させて表を完成させる方が簡便でExcelの本質に即しているとは思いますが、ここではあえて1セルで完結させています。



 基本的な手順については「具体例で学ぶ数学」さんの記事が参考になるものと思います。
 同サイトの例に倣って表記すると、上記式内のLET関数で定義している配列a~cの意味は次のようになります。

・配列aは1つ目の文字列の長さより1つ長い、0から始まる配列
・配列bは2つ目の文字列の長さの、1から始まる配列
・配列cは1つ目の文字列の長さの、1から始まる配列

 配列b,cと2重のREDUCE/LAMBDA関数を組み合わせて2重ループを形成して表の数値を埋めていき、最終的に解答となるいちばん右下の値を求めていきます。
 ただし距離を求めるだけなら上記のような2次元配列(表)を作らずとも配列aを2行目以降の配列(行)で順次更新していけばいいだけなので、ここではそうしています。
 最後にCHOOSECOLSで配列aの末尾(解答)だけを取得しています。



 参考までに各種の文字列の距離を求めた結果です。
 文字数が同じで共通する文字が全くない場合の距離はその文字数となり、全く同じ文字列の距離は0となります。


 なお、CHOOSECOLSを外すと次のような結果になります。上記のように2次元配列(表)の生成を省略していますので、解答(右端)を含む1行の配列しか得られません。

 D3セル

=LET(a,SEQUENCE(1,LEN(B3)+1,0),b,SEQUENCE(LEN(C3)),c,SEQUENCE(LEN(B3)),
REDUCE(a,b,LAMBDA(a,b,
REDUCE(b,c,LAMBDA(b,c,
HSTACK(b,MIN(INDEX(a,c)+(MID(B3,c,1)<>MID(C3,INDEX(b,1),1)),INDEX(a,c+1)+1,INDEX(b,c)+1))
)))))