simstring的python实现,一种简单有效的近似字符串匹配算法。
simstring-pure的Python项目详细描述
模拟字符串
一个Python实现的SimString,一种简单有效的近似字符串匹配算法。
功能
通过这个库,您可以从大量的字符串/文本中提取具有一定相似性的字符串/文本它将帮助您开发与语言处理相关的应用程序。
该库支持cossine相似度、jaccard相似度等多种相似度函数,支持word n-gram和charactern-gram作为特征。您还可以轻松实现自己的特征提取程序。
Simstring具有以下功能:
- 近似字符串检索的快速算法。
- 100%准确检索虽然有些算法允许漏检(误报)以获得更快的查询响应,但simstring可以保证通过快速的查询响应实现100%的正确检索。
- Unicode支持。
- 可扩展性。您可以轻松实现自己的特征提取程序。
- 日本的支持。MeCab
Please see this paper for more details。
安装
pip install simstring-pure
用法
fromsimstring.feature_extractor.character_ngramimportCharacterNgramFeatureExtractorfromsimstring.measure.cosineimportCosineMeasurefromsimstring.database.dictimportDictDatabasefromsimstring.searcherimportSearcherdb=DictDatabase(CharacterNgramFeatureExtractor(2))db.add('foo')db.add('bar')db.add('fooo')searcher=Searcher(db,CosineMeasure())results=searcher.search('foo',0.8)print(results)# => ['foo', 'fooo']
如果要使用其他特性、度量和数据库,只需替换这些类。如果需要,可以用自己的类轻松替换这些类。
fromsimstring.feature_extractor.word_ngramimportWordNgramFeatureExtractorfromsimstring.measure.jaccardimportJaccardMeasurefromsimstring.database.mongoimportMongoDatabasefromsimstring.searcherimportSearcherdb=MongoDatabase(WordNgramFeatureExtractor(2))db.add('You are so cool.')searcher=Searcher(db,JaccardMeasure())results=searcher.search('You are cool.',0.8)print(results)
支持的字符串相似性度量
- 余弦
- 骰子
- 雅卡
运行测试
python -m unittest discover tests
基准
- 从5797个字符串(公司名称)中搜索字符串大约需要1毫秒
- 从235544个字符串(未桥接字典)中搜索字符串大约需要14毫秒。
从dev/data/company_names.txt
搜索
$ python dev/benchmark.py
benchmark for using dict as database
## benchmarker: release 4.0.1 (for python)
## python version: 3.7.0
## python compiler: GCC 7.2.0
## python platform: Linux-4.9.87-linuxkit-aufs-x86_64-with-debian-9.4
## python executable: /opt/conda/envs/simstring/bin/python
## cpu model: Intel(R) Core(TM) i7-6567U CPU @ 3.30GHz # 3300.000 MHz
## parameters: loop=1, cycle=1, extra=0
## real (total = user + sys)
initialize database(5797 lines) 0.1227 0.1200 0.1200 0.0000
search text(5797 times) 6.9719 6.9400 6.8900 0.0500
## Ranking real
initialize database(5797 lines) 0.1227 (100.0) ********************
search text(5797 times) 6.9719 ( 1.8)
## Matrix real [01] [02]
[01] initialize database(5797 lines) 0.1227 100.0 5680.9
[02] search text(5797 times) 6.9719 1.8 100.0
benchmark for using Mongo as database
## benchmarker: release 4.0.1 (for python)
## python version: 3.7.0
## python compiler: GCC 7.2.0
## python platform: Linux-4.9.87-linuxkit-aufs-x86_64-with-debian-9.4
## python executable: /opt/conda/envs/simstring/bin/python
## cpu model: Intel(R) Core(TM) i7-6567U CPU @ 3.30GHz # 3300.000 MHz
## parameters: loop=1, cycle=1, extra=0
## real (total = user + sys)
initialize database(5797 lines) 4.5762 2.4900 1.9200 0.5700
search text(5797 times) 177.8401 60.9100 47.2500 13.6600
## Ranking real
initialize database(5797 lines) 4.5762 (100.0) ********************
search text(5797 times) 177.8401 ( 2.6) *
## Matrix real [01] [02]
[01] initialize database(5797 lines) 4.5762 100.0 3886.2
[02] search text(5797 times) 177.8401 2.6 100.0
从dev/data/unabridged_dictionary.txt
搜索
$ python dev/benchmark.py
benchmark for using dict as database
## benchmarker: release 4.0.1 (for python)
## python version: 3.7.0
## python compiler: GCC 7.2.0
## python platform: Linux-4.9.87-linuxkit-aufs-x86_64-with-debian-9.4
## python executable: /opt/conda/envs/simstring/bin/python
## cpu model: Intel(R) Core(TM) i7-6567U CPU @ 3.30GHz # 3300.000 MHz
## parameters: loop=1, cycle=1, extra=0
## real (total = user + sys)
initialize database(235544 lines) 2.2576 2.2300 2.1200 0.1100
search text(10000 times) 141.0302 140.6400 139.9600 0.6800
## Ranking real
initialize database(235544 lines) 2.2576 (100.0) ********************
search text(10000 times) 141.0302 ( 1.6)
## Matrix real [01] [02]
[01] initialize database(235544 lines) 2.2576 100.0 6246.8
[02] search text(10000 times) 141.0302 1.6 100.0