字符串匹配

Question

让我解释一下这个问题：

1. 假设我有一个图书馆，图书馆里有很多书，每本书都有章节，每一章都有字符串(字符串以点开头和结尾)。
2. 该序列再次，库->图书->章节->字符串。
3. 我从书中提取字符串，让我们称它们为“书本字符串”。
4. 我有一个系统，用户可以在搜索表单中输入一个字符串，系统应该从“图书字符串”返回输入字符串的准确匹配。如果输入的字符串与图书字符串中的任何字符串不匹配，则不会返回任何字符串。

考虑一下，我找到了一个解决方案，我将MD5所有的图书字符串，并保存散列的图书字符串。当用户输入要搜索的字符串时，我也会散列它，并在散列的图书字符串中搜索匹配项。它更便宜(每个字符串有32个或64个字符)，比普通搜索更快，而且它只返回准确的匹配(Es)。

有什么意见，想法，更好的解决方案吗？

这种算法的名称是什么？搜索还是匹配？

Answer 1

不错，但你应该调查露茜。它是一个以多种语言实现的公共共享软件文本索引和搜索工具，其中之一是.Net。(你在哪个平台/语言工作？)我用它在公共互联网上对网站内容进行免费文本搜索，其主要模式是在市场细分市场提供内容(许多杂志文章、图书摘录等)。露茜为我们工作得很好。

卢塞尼

Answer 2

在字符串中搜索的算法有很多，从简单的方法(如博耶-摩尔算法)到复杂的数据结构(如后缀树 )。对这些问题的全面介绍可在以下文件中找到：

• Gusfield，Dan (1999)，关于字符串、序列和树的算法。剑桥:大学出版社。

但是，就您的情况而言，将图书文本拆分为单独的标记(单词)并将它们存储在索引中(例如，简单地在Map中，或者使用完整的框架进行索引和搜索，如卢塞尼)可能更有意义。

Answer 3

它被称为散列，可以被认为是搜索或匹配。

您应该通过比较用于生成哈希的字符串来验证MD5哈希是否正确，因此您没有任何假阳性。

另一件需要考虑的事情是，支持某种类型的，从搜索开始，这可能是有益的。

Mary Queen of Scots
Mary Livingston
Mary Had a Little Lamb, and other silly stories

以搜索开始寻找玛丽，应该返回这三条记录，可能还有更多。虽然MD5类型的哈希是快速的，但在其他答案中提供的技术也应该被考虑，以便为您的环境找到最佳的效益/成本平衡。