函数检查字符串与字符串列表的相似性。

Question

我在一个存储桶中有一个类似字符串的集合，并且有多个这样的存储桶。我应该在字符串上使用哪种函数来将随机字符串与存储桶进行比较，以找出它属于哪个存储桶？

为了澄清桶中的每个实体，它是一个可以有多个单词的句子。

举个例子：

考虑存储桶中的字符串列表：

1. 圆领黑色t恤
2. 印花T恤
3. 棕色马球t恤

如果我们有“蓝色高领t恤”作为输入，我们希望检查是否可以将其添加到相同的存储桶中。这可能是一个更简单的例子，但请考虑对一桶字符串执行此操作，比如说100个字符串。

任何对一篇文章或论文的引用都会很有帮助。

Answer 1

首先，我认为有两种相似之处:句法和语义。

1)语法

• Levenstein distance可以用来测量两个序列之间的距离( characters)
• Stemming可以用来增加匹配概率)。有多种实现(例如here)。您可以获取随机字符串的词干(或词根)，并将其与存储桶中的词干进行比较。当然，为了提高效率，应该预先计算桶干。

2)语义

• 有关一般信息，您可以阅读article from Wikipedia
• 以了解实际实现。您可以从CodeProject阅读this article。它基于WordNet，这是一个很棒的英语本体，它将概念存储在同义词集中，并提供这些同义词之间的各种关系。

为了获得更多的细节，你应该告诉我们你需要什么样的相似性。

编辑

根据提供的信息，我认为您可以这样做：

1)将所有字符串拆分成单词和随机字符串，命名为Array1 => current bucket Array2

2)相似度计算为number_of_common_words(Array1，Array2) / count(Array2)

3)选择最大相似度

也可以通过将点添加到位置匹配来提高特异性: Array1i = Array2i

为了获得更好的性能，我会将存储桶存储为Hash tables、Dictionary等，以便在O(1)中完成存在检查。