英文:
String similarity algorithms
问题
我正在比较多家商店的产品。我只能访问产品名称 - 但在各个商店之间通常会有所不同。例如：商店 1 可能将产品列为“iPhone 14 Midnight 128GB”，而商店 2 则将其列为“Apple iPhone 14 (128GB) - Midnight - NEW”。
对于这个任务，通常的字符串比较如Levenshtein距离并不特别适用。我在将单词分开，去除特殊字符，然后分别计算每个单词的Levenshtein距离方面取得了最大的成功。
有没有一个适合这个任务的算法/库？
英文:
I am comparing products across multiple stores. I only have access to the product name - which often differs between stores. For example: Store 1 might list a product as "iPhone 14 Midnight 128GB" whereas Store 2 lists it as "Apple iPhone 14 (128GB) - Midnight - NEW".
Typical string comparisons such as Levenshtein distance don't work particularly well for this task. I've had the most success with separating words, removing special characters, then calculating the Levenshtein distance for each word individually.
Is there an algorithm/library that would work well for this task?
答案1
得分: 2
为了实现这个目的，您可以使用三元模糊搜索算法。该算法的思想是将字符串分割成相交的三元组，并计算最大的交集分数。
大约20年前，John Wilbur设计了这个算法，我编写了它的实现，您可以下载我的实现，即Wilbur-Khovayko算法。
这个实现可以搜索输入搜索词的“N个最接近的词”。
词汇列表 - 在文件termlist.txt中 N - 在变量lim中，文件findtest.c
该算法非常快速：在旧的Sun 200mHz上，它可以在大约0.3秒内搜索100,000个条目中的100个最接近的词。
英文:
For this purpose, you can use trigram fuzzy search algorithm. Idea of this algorithm: split string to intersected trigrams, and compute maximal intersection score.
~20 years ago John Wilbur designed, and I I wrote implementation of this algorithm, you can download my implementation of this Wilbur-Khovayko algorithm.
This implementation search "N closest terms" for entered search term.
List of terms - in the file termlist.txt N - in the variable lim, file findtest.c
Algorithm is very quick: on the old Sun 200mHz, it search 100 closest term among 100,000 entries for ~0.3 secs.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论