Pat

J-GLOBAL ID：200903074200299280

文字列比較方法

Inventor： 太田 博志
Applicant, Patent owner： 日本電気株式会社
Agent (1)： 後藤 洋介 (外2名)
Gazette classification：公開公報
Application number (International application number)：1992230516
Publication number (International publication number)：1994083871
Application date： Aug. 28, 1992
Publication date： Mar. 25, 1994
Summary：

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

Claim (excerpt)：

長さ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に変換するコストと併せ、文字列の近似度とすることを特徴とする文字列比較方法。