TSfree 発言

On Sun, 21 Oct 2007 04:54:03 +0900
"Bruce." <kbk@...> さんwrote:

> 「似たような文字列を検索する」というのはいろいろアルゴリズムが開発されてますよ。
> 
> A dictionary for approximate string search and longest prefix search
> http://portal.acm.org/citation.cfm?id=1183614.1183723
> 
> CiNii - Full Text Approximate String Search using Suffix Arrays
> http://ci.nii.ac.jp/naid/110002934590/en/
> 
> Approximate string-matching approaches
> http://www.cse.unsw.edu.au/~waleed/phd/html/node167.html
> 
> agrepなんかはこういったものの一つ(かいくつかの手法の組み合わせ)を使っていた
> はずです。

前に紹介した、String::Approxはagrepと同様な検索アルゴリズムを使ったもの
と思われます。ACKNOWLEDGEMENTSによると

The matching algorithm was developed by Udi Manber, Sun Wu, and Burra
Gopal in the Department of Computer Science, University of Arizona.

とされており、

Algorithms used in AGREP
http://www.tgries.de/agrep/#ALGORITHMS

の著者と同じメンバーだからです。

String::Approxのマニュアルから他のモジュールにも言及があるので引用してお
きましょう。

If you want to compare strings for similarity, you probably just want
the Levenshtein edit distance (explained below), the Text::Levenshtein
and Text::LevenshteinXS modules in CPAN. See also Text::WagnerFischer
and Text::PhraseDistance. (There are functions for this in String::Approx,
e.g. adist(), but their results sometimes differ from the bare
Levenshtein et al.)

If you want to compare things like text or source code, consisting of
words or tokens and phrases and sentences, or expressions and
statements, you should probably use some other tool than String::Approx,
like for example the standard UNIX diff(1) tool, or the Algorithm::Diff
module from CPAN.

前のでびさんの「[TSfree:2240] Re: 最も人気あるプログラミング言語」に出て
くる「レーベンシュタイン距離」についてもいろいろと実装があるようですし、
String::Approxも取り扱うようです。

おそらく、辞書を参照するタイプのものは日本語に適用するのは辞書を準備する
必要があるためにすぐに利用することは難しいでしょう。文字列を取り扱うもの
か、日本語に適用した実績のあるものなら使えるでしょうね。

String::Approxは日本語でもテキストをUTF-8で保存して適用すれば使えると思
われます。

藤岡 和夫
kazuf@...
日曜プログラマのひとりごと http://homepage1.nifty.com/kazuf/renewal.html