SimStringは，類似文字列検索のための高速かつシンプルなライブラリです． 類似文字列検索とは，文字列集合（データベース）の中から，クエリ文字列との類似度が閾値以上のものを，見つけ出す操作です． クエリ文字列と完全に一致しなくても，データベース中の似ている文字列を検索することができるので，スペル訂正，あいまい計算，柔軟な辞書マッチング，重複レコード検出，データベース統合など，様々なアプリケーションを構築できます．
SimStringは，類似度関数として，コサイン係数，ジャッカード係数，ダイス係数，オーバーラップ係数に対応しています． 文字列の類似度を計算するための特徴量としては，文字nグラムをサポートしています．
SimStringには，次のような特徴があります．
- 高速な類似文字列検索アルゴリズム．Google Web1T の英語単語（13,588,391文字列）から，コサイン類似度が0.7以上の文字列を検索するのに必要な時間は，１クエリあたり 1.10 [ms] 程度です（Intel Xeon 5140 2.33 GHz CPUにおいて）．
- 100%正確な類似文字列検索．類似文字列検索アルゴリズムの中には，検索漏れを許容することで，検索を高速化する方法がありますが，SimStringは100%正確な検索を保証しつつ，高速なクエリ性能を実現しています．
- ユニコード（wchar_t）への対応．日本語と英語では一文字の表現に要するバイト数が異なるため，SimStringでは１バイト文字（char）に加え，ユニコード文字（wchar_t）を文字の表現に利用することができます．
- C++ヘッダによる実装．SimStringはすべてC++のヘッダファイルとして実装されています．したがって，一つのヘッダファイルをソースコードにインクルードするだけで，SimStringのライブラリが使えるようになります．
- SWIGによるPython/Rubyライブラリの提供．スクリプト言語上で，SimStringデータベースの構築・検索が，簡単にできます．
現在のSimStringのバージョンは1.0です．
SimStringは修正BSDライセンスで配布されます．
このソフトウェアを引用する場合は，次のBibTexエントリを利用してください．
@inproceedings{SimString,
author = {岡崎直観 and 辻井潤一},
title = {高速な類似文字列検索アルゴリズム},
booktitle = {情報処理学会創立50周年記念全国大会},
pages = {1C-1},
url = {http://www.chokkan.org/software/simstring/},
year = {2010}
}
一般的なconfigure & makeでビルドできます．
simstringユーティリティのソースコードは，frontend/main.cppにあります．
makeをすると，実行ファイルfrontend/simstringが作られます．
$ ./configure $ make $ make install
SimStringを利用するC++プログラムをコンパイルするときに，配布パッケージのincludeディレクトリをインクルードディレクトリに追加してください．
もしくは，上の手順でmake installを実行すると，標準インクルードディレクトリにSimStringがインストールされます．
SimStringライブラリの使い方については，C++のサンプルプログラム，simstringユーティリティのソースコード（frontend/main.cpp），SimStringのAPIドキュメンテーションを参照してください．ほとんどの場合は，サンプルプログラムを読むだけで事足りると思います．
SWIGモジュールの利用方法は，SimStringモジュールのサンプルプログラム，SimStringのSWIGモジュール・ドキュメンテーションを参照してください．ほとんどの場合は，サンプルプログラムを読むだけで事足りると思います． ビルド方法は，各言語によって異なりますので，個別に説明します． 現在，PythonとRubyを公式にサポートしていますが，SWIGですので，他の言語のモジュールを作るのは容易だと思います． （私はPythonしか書けませんので，他の言語に詳しい方は，ビルド方法やサンプルプログラムなどを送って頂けると助かります．）
以下の手順で，simstring.pyと_simstring.soをビルドし，インストールします．
$ ./configure $ cd swig/python $ ./prepare.sh $ python setup.py build_ext $ python setup.py install
なお，モジュールをビルドするコマンド（build_ext）に，--inplaceオプションを追加すると，simstring.pyと_simstring.soがカレントディレクトリにビルドされます．そのディレクトリがモジュール検索パスに登録されているなら（たとえば，pythonを実行したときのカレントディレクトリはモジュール検索パスに含まれています），モジュールをインストールすることなく，SimStringを試すことができます．
Google Web 1Tコーパスの英語単語列（web1tuni.txt）から，SimStringデータベース（web1tuni/web1tuni.db）を構築する例．
simstringユーティリティは，標準入力から１行１文字列として，文字列集合を読み込みます．
simstringユーティリティの詳しい利用方法は，-hオプションで確認してください．
$ simstring -b -d web1tuni/web1tuni.db < web1tuni.txt SimString 1.0 Copyright (c) 2009,2010 Naoaki Okazaki Constructing the database Database name: web1tuni/web1tuni.db N-gram length: 3 Begin/end marks: false Char type: c (1) Number of strings: 10000 Number of strings: 20000 Number of strings: 30000 ... Number of strings: 13570000 Number of strings: 13580000 Number of strings: 13588391 Flushing the database Total number of strings: 13588391 Seconds required: 221.76
上で構築したデータベース（web1tuni/web1tuni.db）に対して，コサイン類似度が0.9以上の文字列を検索する例．標準入力からクエリ文字列を読み込み，検索された文字列を出力します．この例では，「approximate」に対して12文字列，「string」に対して1文字列，「retrieval」に対して5文字列が一瞬で検索されています．
$ simstring -d web1tuni/web1tuni.db -t 0.9 -s cosine
approximate
approximat
pproximate
approximate
approximated
approximatel
approximates
approximatey
anapproximate
approximatelt
approximately
reapproximate
toapproximate
12 strings retrieved (0 sec)
string
string
1 strings retrieved (0 sec)
retrieval
etrieval
retrieva
retrieval
retrieval.
retrievals
5 strings retrieved (0 sec)
SimStringのデータベースをユニコードで構築する例．
simstringユーティリティに-uオプションを追加すると，文字の表現にユニコード（wchar_t）が用いられるようになります．
以下の例では，日本語N-gramデータ中の日本語の語（web1tja/strings.txt）から，SimStringデータベース（web1tja/unigrams.db）を構築します．
$ simstring -bu -d web1tja/unigrams.db < web1tja/strings.txt SimString 1.0 Copyright (c) 2009,2010 Naoaki Okazaki Constructing the database Database name: web1tja/unigrams.db N-gram length: 3 Begin/end marks: false Char type: w (4) Number of strings: 10000 Number of strings: 20000 Number of strings: 30000 ... Number of strings: 2560000 Number of strings: 2565424 Flushing the database Total number of strings: 2565424 Seconds required: 32.45
SimStringのデータベースをユニコードで検索する例です． データベース構築の時と同様に，simstringユーティリティに-uオプションを追加してください．
$ simstring -u -d web1tja/unigrams.db -t 0.7 -s cosine
スパゲッティー
スパゲッティ
スパゲッテー
スパゲティー
スパッティー
スパゲッティー
スパゲッティーニ
スパゲッティー・
スパッゲッティー
スパゲッティーニ・
・・スパゲッティー
スープスパゲッティー
スパゲッティーモンスター
12 strings retrieved (0 sec)
フェットチーネ
フェットチー
フェトチーネ
フットチーネ
フェットチーネ
フェットゥチーネ
フェットチーネ・
フェット・チーネ
フェットゥッチーネ
8 strings retrieved (0 sec)
SimStringをPythonの対話シェルで利用する例． SWIGでビルドしたsimstringモジュールをimportし，上の例で構築したデータベースを開き，類似文字列検索を行っています．
$ python
Python 2.5.1 (r251:54863, Oct 15 2007, 23:38:19)
[GCC 3.4.6 20060404 (Red Hat 3.4.6-8)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import simstring
>>> db = simstring.reader('web1tuni/web1tuni.db')
>>> db.measure = simstring.cosine
>>> db.threshold = 0.9
>>> db.retrieve('approximate')
('approximat', 'pproximate', 'approximate', 'approximated', 'approximatel', 'appr
oximates', 'approximatey', 'anapproximate', 'approximatelt', 'approximately', 're
approximate', 'toapproximate')
>>> db = simstring.reader('web1tja/unigrams.db')
>>> db.measure = simstring.cosine
>>> db.threshold = 0.7
>>> print(' '.join(db.retrieve('スパゲッティー')))
スパゲッティ スパゲッテー スパゲティー スパッティー スパゲッティー スパゲッティー
ニ スパゲッティー・ スパッゲッティー スパゲッティーニ・ ・・スパゲッティー スープ
スパゲッティー スパゲッティーモンスター
>>>