如何在大型字符串数据库中找到字符串的最佳模糊匹配 [英] How to find best fuzzy match for a string in a large string database

问题描述

我有一个字符串数据库(任意长度)，其中包含超过一百万个项目(可能更多).

我需要将用户提供的字符串与整个数据库进行比较，并检索相同的字符串(如果存在)，否则返回最接近的模糊匹配(相似度为60％或更高).理想情况下，搜索时间应在一秒以内.

我的想法是在根据候选数据库的长度缩小候选数据库的范围后，使用编辑距离将每个数据库字符串与搜索字符串进行比较.

但是，由于我将需要经常执行此操作，因此我正在考虑构建数据库字符串的索引以保留在内存中并查询该索引，而不是直接查询数据库.

关于如何以不同方式处理此问题或如何建立内存索引的任何想法吗?

解决方案

本文似乎准确地描述了您想要的内容.

Lucene( http://lucene.apache.org/)也实现了Levenshtein的编辑距离.

I have a database of strings (arbitrary length) which holds more than one million items (potentially more).

I need to compare a user-provided string against the whole database and retrieve an identical string if it exists or otherwise return the closest fuzzy match(es) (60% similarity or better). The search time should ideally be under one second.

My idea is to use edit distance for comparing each db string to the search string after narrowing down the candidates from the db based on their length.

However, as I will need to perform this operation very often, I'm thinking about building an index of the db strings to keep in memory and query the index, not the db directly.

Any ideas on how to approach this problem differently or how to build the in-memory index?

解决方案

This paper seems to describe exactly what you want.

Lucene (http://lucene.apache.org/) also implements Levenshtein edit distance.

这篇关于如何在大型字符串数据库中找到字符串的最佳模糊匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！