1

我有大量文档、文本文件，我想搜索相关内容。我见过一个搜索工具，不记得在哪里，它实现了一个很好的方法，正如我在下面的要求中描述的那样。

我的要求如下：

  • 我需要一个优化的搜索功能：我为这个搜索功能提供了一个列表（一个或多个）部分完整（或完整）的单词，用空格分隔。
  • 然后该函数查找包含与第一个单词开头或等于第一个单词的单词的所有文档，然后使用第二个单词以相同的方式搜索这些找到的文档，依此类推，最后它返回一个列表，其中包含找到的实际单词链接包含它们的文件（名称和位置），以获取完整的单词列表。
  • 文件必须包含列表中的所有单词。
  • 我想使用此功能进行即时搜索，以便我可以实时显示和更新树状结构中的结果。

我想出的解决方案的一种可能方法如下：我创建了一个包含三个表的数据库（很可能使用 mysql）：'Documents'、'Words' 和 'Word_Docs'。

  • “文档”将包含所有文档的（idDoc、名称、位置）。
  • 'Words' 将具有 (idWord, Word) ，并且是所有文档中唯一单词的列表（特定单词仅出现一次）。
  • 'Word_Docs' 将具有 (idWord, idDoc) ，并且是它出现的每个单词和文档的唯一 id 组合列表。

然后在每次击键时使用编辑框的内容调用该函数（空格除外）：

  • 字符串被标记化
  • （这里我的轮子旋转了一下）：我确信可以构造一条 SQL 语句来返回所需的数据集：（actual_words，doc_name，doc_location）；（我不是 SQL 的热门号码），或者对每个令牌进行一系列调用并解析出非重复的 idDocs？
  • 然后返回此数据集（/list/array）

然后显示返回的列表内容：

例如：调用：“seq sta cod”显示：

sequence - start - code - Counting Sequences [file://docs/sample/con_seq.txt]
         - stop - code - Counting Sequences [file://docs/sample/con_seq.txt]
sequential - statement - code - SQL intro [file://somewhere/sql_intro.doc]

（等等）

这是一种最佳的做法吗？该函数需要快速，还是应该仅在命中空格时调用？它应该提供单词完成吗？（得到数据库中的单词）至少这可以防止对不存在的单词的函数进行无用的调用。如果单词完成：将如何实施？

（也许 SO 也可以使用这种类型的搜索解决方案来浏览标签？（在主页的右上角））

4

4 回答 4

2

最快的方法当然是根本不使用数据库，因为如果您使用优化的数据手动进行搜索，您可以轻松击败选择搜索的性能。假设文档不经常更改，最快的方法是构建索引文件并使用它们来查找关键字。索引文件是这样创建的：

  1. 查找文本文件中的所有唯一词。即按空格将文本文件拆分为单词，并将每个单词添加到列表中，除非已在该列表中找到。

  2. 把你找到的所有单词按字母顺序排序；最快的方法是使用三向基数快速排序。在对字符串进行排序时，这种算法在性能上很难被击败。

  3. 将排序后的列表写入磁盘，一行一个字。

  4. 当您现在要搜索文档文件时，完全忽略它，而是将索引文件加载到内存中并使用二进制搜索来找出索引文件中是否存在单词。在搜索大型排序列表时，二进制搜索很难被击败。

或者，您可以在一个步骤中合并步骤 (1) 和步骤 (2)。如果您使用 InsertionSort（它使用二进制搜索来找到正确的插入位置以将新元素插入到已排序的列表中），您不仅有一个快速算法来确定单词是否已经在列表中，以防万一不是，您会立即获得插入它的正确位置，如果您总是像这样插入新的，当您进入步骤 (3) 时，您将自动获得一个排序列表。

问题是每当文档更改时您都需要更新索引......但是，这对于数据库解决方案是否也是如此？另一方面，数据库解决方案为您带来了一些优势：您可以使用它，即使文档包含这么多单词，索引文件也不再适合内存（不太可能，因为即使是所有英文单词的列表也会适合任何普通用户 PC 的内存）；但是，如果您需要加载大量文档的索引文件，那么内存可能会成为问题。好的，您可以使用巧妙的技巧来解决这个问题（例如，直接在使用 mmap 等映射到内存的文件中搜索），但这些技巧与数据库已经用于执行快速查找的技巧相同，那么为什么要重新发明轮子呢？此外，您还可以防止在文档更改时搜索单词和更新索引之间的锁定问题（即，如果数据库可以为您执行锁定，或者可以将更新或更新作为原子操作执行）。对于使用 AJAX 调用列表更新的 Web 解决方案，使用数据库可能是更好的解决方案（如果这是用 C 等低级语言编写的本地运行应用程序，我的第一个解决方案非常合适）。

如果您想在一次选择调用中完成所有操作（这可能不是最佳的，但是当您使用 AJAX 动态更新 Web 内容时，它通常被证明是最不让人头疼的解决方案），您需要将所有三个表连接在一起。可能 SQL 有点生疏，但我会试一试：

SELECT COUNT(Document.idDoc) AS NumOfHits, Documents.Name AS Name, Documents.Location AS Location 
FROM Documents INNER JOIN Word_Docs ON Word_Docs.idDoc=Documents.idDoc 
INNER JOIN Words ON Words.idWord=Words_Docs.idWord
WHERE Words.Word IN ('Word1', 'Word2', 'Word3', ..., 'WordX')
GROUP BY Document.idDoc HAVING NumOfHits=X

好吧，也许这不是最快的选择......我想它可以做得更快。无论如何，它会找到所有匹配的文档，其中至少包含一个单词，然后将所有相等的文档按 ID 分组在一起，统计有多少已被分组 togetehr，最后只显示 NumOfHits（IN 语句找到的单词数）的结果等于 IN 语句中的字数（如果搜索 10 个字，则 X 为 10）。

于 2008-09-29T09:31:58.723 回答
2

您所说的内容称为倒排索引或发布列表，其运作方式与您的建议和 Mecki 的建议类似。有很多关于倒排索引的文献。维基百科文章是一个很好的起点。

更好的是，与其尝试自己构建它，不如使用现有的倒排索引实现。默认情况下，MySQL 和最新版本的 PostgreSQL 都具有全文索引。您可能还想查看Lucene以获得独立的解决方案。编写一个好的倒排索引需要考虑很多事情，包括标记化、词干提取、多词查询等，而预构建的解决方案将为您完成所有这些工作。

于 2008-09-29T10:11:22.917 回答
0

不确定语法（这是 sql server 语法），但是：

-- N is the number of elements in the list

SELECT idDoc, COUNT(1)
FROM Word_Docs wd INNER JOIN Words w on w.idWord = wd.idWord
WHERE w.Word IN ('word1', ..., 'wordN')
GROUP BY wd.idDoc
HAVING COUNT(1) = N

也就是说，不使用like。类似的事情要复杂得多。

于 2008-09-29T08:47:51.683 回答
0

Google 桌面搜索或类似工具可能会满足您的要求。

于 2008-09-29T09:45:05.307 回答