文字列検索アルゴリズムの覚え書き - 我らねぶた馬鹿
マイコミジャーナルの連載記事で、「StringSearch」という文字列検索のためのJavaライブラリを紹介しました。 攻略! ツール・ド・プログラミング (44) 高速な文字列検索を実現するJavaライブラリ「StringSearch」 | マイナビニュース その補足も兼ねて、記事中に出てくる文字列検索アルゴリズムについて少しまとめてみました。細部を省略した大雑把な説明なので厳密な解説ではありませんが、参考までに。 naiveアルゴリズム 対象の文字列とパターン文字列を先頭から順番に比べていき、マッチしなかったら1文字進めてまた最初から比べるという手法です。 java.lang.StringのindexOf()メソッドなどはこの実装だそうです。 Knuth Morris Pattアルゴリズム（KMPアルゴリズム） マッチに失敗した場合に、比較するスタート位置を1文字ずつ進めるではなく、何
List::FrontCode - naoyaのはてなダイアリー
先日 Array::Gap という Variable Byte Codes による整列済み整数の圧縮の実装を作りました。(id:naoya:20080906:1220685978) 今日は Front Coding を使った同じような圧縮リストクラス、List::FrontCode を作ってみました。Front Coding は辞書式順に整列済みの文字列リストなどを圧縮する手法です。WEB+DB PRESS Vol.42 のアルゴリズム&データ構造の記事で PFI の岡野原さんによる解説があったので、それを参考に実装しました。 Front Coding Front Coding は http://www.hoge.jp http://www.hoge.jp/a.htm http://www.hoge.jp/index.htm http://www.fuga.com/ http://www.
Twitter本文と言及URLの圧縮 - kaisehのブログ
最近、Twitterのデータを収集しています。APIで取得したtweet本文や、そこから抽出したURLを片っ端からDBに保存していくと件数が莫大になるので、ディスクスペースを極力節約したいところですが、個別のtweet本文や言及URLは短い文字列なので、普通に1件ずつgzip等で圧縮してもほとんど意味がないか、オーバーヘッドが出て逆効果になってしまいます。 そこで、収集済みのサンプルデータを元にハフマン木を作っておき、それを共通利用してtweetを圧縮してみました。 用意したのは、英語ユーザ/日本語ユーザ/韓国語ユーザ各1000人のtweetサンプルをベースにしたハフマン符号と、tweet本文から抽出したURL文字列をベースにしたハフマン符号の4種類です。 頻度表は次のようになりました。 char (en) freq (en) char (ja) freq (ja) char (ko) f
【コラム】攻略! ツール・ド・プログラミング (44) 高速な文字列検索を実現するJavaライブラリ「StringSearch」 | エンタープライズ | マイコミジャーナル
各種文字列検索アルゴリズムを実装したStringSearch Johann Burkard氏が公開しているStringSearchは、高速な文字列検索アルゴリズムを実装したJava用ライブラリである。BNDM法や、BMH法とその派生、Bit-parallel手法といった複数のアルゴリズムをサポートしている点が特徴。いずれのアルゴリズムを利用する場合でも基本的な使い方は共通しているため、用途によって簡単に使い分けることができる。 Burkard氏によれば、StringSearchを利用すればjava.lang.Stringクラスによる文字列検索に比べて5倍から10倍程度の高速化が可能とのことである。ただし、この主張には異論も出ている。また、String.indexOf()メソッドなどで採用されているというnaiveアルゴリズム(シンプルだが低速)にしても、短い文字列を対象とした検索であれば十
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
robert-bor/aho-corasick · GitHub - Java implementation of the Aho-Corasick algorithm for efficient string matching
An efficient compression algorithm for short text strings
