8

There have been numerous posts on string algorithms:

However, no general literature was mentioned.

Could anyone recommend a book(s) that would thoroughly explore various string algorithms? The topic which is of special interest is approximate string matching [things like google-offered corrected search string variants :) ].

Thanks a lot for advice.

4

5 に答える 5

8

Dan Gusfield の優れた本Algorithms on Strings, Trees and Sequencesについて誰も言及していないことに驚いています。それは、私が数年前に取り組んでいたタンパク質配列決定に関するプロジェクトに非常に役立ちました. この本を読むと、次のことがわかります。

  • 単純な文字列マッチング
  • プリプロセッサ ベースのアルゴリズム (Boyer Moore、Knuth-Morris-Pratt)
  • 正規表現一致アルゴリズム
  • Karp-Rabin および類似の方法
  • サフィックスツリー法（ウッコネン法など）
  • 配列アラインメント (レーベンシュタイン距離と文字列類似性、複数の配列アラインメント)
  • DNAシーケンシング、遺伝子予測、その他の分野への応用。
于 2010-05-11T19:01:05.977 に答える
2

これは書籍の推奨事項ではありませんが、このライブラリとサイトは、効率的な文字列一致アルゴリズムの実装を多数提供するライブラリです。

http://www.dcs.shef.ac.uk/~sam/simmetrics.html

また、それぞれの詳細学習へのリンクと、それぞれが最も適している場所も提供します。

于 2010-05-11T18:50:16.833 に答える
2

ストリングロジーの宝石

于 2010-05-11T20:48:15.653 に答える
1

TREは、近似マッチングを実装するオープンソース ライブラリです。Aboutページには、それがどのように機能するかについての興味深いヒントがいくつかありますが、あなたが探しているような詳細な分析が提供されているかどうかはわかりません. ソースコードは、おそらくその観点からより啓発的です。

于 2010-05-11T18:44:59.663 に答える
1

CLRにはいくつかの文字列処理アルゴリズムがありますが、それらに固有のものではありません。

含む：

于 2010-05-11T18:33:56.690 に答える