特許

J-GLOBAL ID：200903074200299280

文字列比較方法

発明者： 太田 博志
出願人/特許権者： 日本電気株式会社
代理人 (1件)： 後藤 洋介 (外2名)
公報種別：公開公報
出願番号（国際出願番号）：特願平4-230516
公開番号（公開出願番号）：特開平6-083871
出願日： 1992年08月28日
公開日（公表日）： 1994年03月25日
要約：

【要約】【目的】 Levenstein距離を求める方法において、2つの文字列の近似度を文字の連続性を考慮して判定すること。【構成】 部分一致長を格納する配列Mを設定し、配列M’を初期化ステップ2で配列要素を0に初期化し、演算ステップ4で配列要素M’〔i,j〕の値を被比較文字列のi番目の文字と比較文字列のj番目の文字が等しい場合は、M〔i-1,j-1〕に1を加算した値とし、配列Mの最大値が部分文字列一致の最大長を求めることにより、より正確な近似度が求まる。

請求項（抜粋）：

長さmの被比較文字列aと、長さnの比較文字列bの近似度を、文字の追加、削除、変更のそれぞれに対しコストを設定し、行の大きさがm+1、列の大きさがn+1であるコスト配列Mを用意した後、第0列目の配列要素M〔i,0〕(0≦i≦m)の値をそれぞれi×削除、のコストとし、配列要素M〔0,j〕(0≦j≦n)の値をそれぞれj×追加、のコストとするコスト配列初期化ステップと、配列要素M〔i,j〕(0<i≦m,0<j≦n)の値を配列要素M〔i-1,j-1〕の値に、被比較文字列aの第i番目の文字と比較文字列bの第j番目の文字が等しい場合は0、異なる場合は変更のコストを加算した値、配列要素M〔i,j-1〕の値に追加のコストを加算した値、配列要素M〔i-1,j〕の値に削除のコストを加算した値、の3つの値のうちの最小値となるように順に求めていくコスト演算ステップとを有し、このコスト演算ステップによって求められた文字列bを文字列aに変換するコストを以って文字列aと文字列bの近似度とする文字列の比較方法において、さらに、前記コスト配列Mと同じ大きさの部分一致配列M’を用意し、部分一致配列M’の配列要素全てを0で初期化する部分一致配列初期化ステップと、配列要素M’〔i,j〕(0<i≦m,0<j≦n)の値を被比較文字列aのi番目の文字と比較文字列bのj番目の文字が等しい場合には配列要素M’〔i-1,j-1〕の値に1を加算した値とする部分一致演算ステップとを備え、この部分一致演算ステップによって求められた部分一致の最大長を、文字列bを文字列aに変換するコストと併せ、文字列の近似度とすることを特徴とする文字列比較方法。