0

我有以下设计问题：

假设我有 100 万个大小约为 10KB 的纯文本文件。我的目标是设计一种方法来存储所有单词的索引，这样我就可以将每个单词链接到特定的文本文件和单词在所述文件中的位置。

例子：

Text file X contents: "The quick brown fox jumps over the lazy dog"
                       0   1     2     3   4     5    6   7    8

Text file Y contents: "Now is the time for all good men"
                       0   1  2   3    4   5   6    7

我想大致存储以下内容：

the   => {X,0}, {X,6}, {Y,2}
quick => {X,1}
is    => {Y,1}
.... and so on

显然，我实际上并没有索引纯文本文件，我的索引器是一个多线程 C# 应用程序，它将输入提取到术语“文件”、“单词”、“位置”。我无法创建典型的查找表集，因为行数很容易超过 20 亿。

起初我的想法是将对 {message,position} 存储在以单词本身为主键的文本 blob 中。然而，有了这个解决方案，当我的所有线程都尝试用新的 {message,position} 对更新“the”的行时，我担心会有很大的争用。

我被锁定在我的环境中，SQL Server Express 2012，所以让我们使用我们所拥有的。我可以对数据库本身做任何事情，事实上我的应用程序创建数据库作为正常工作流程的一部分，因此如果需要我可以部署 CLR 存储过程。

想法？

4

5 回答 5

1

只是为了扔掉一些东西，创建一个每个文件一行的表。使用xml列存储文件的单词出现次数。

第二张表是你的单词表。通过添加可让您快速定位哪些文件包含哪些单词的交叉引用表来进行非规范化。

现在你可以把它扔掉了。

于 2012-07-11T03:39:24.733 回答
1

我会尝试这样的事情......创建一个带有word/file-id的关联表。每条记录都有两个 id 加上一个完全由 0 和 1 组成的字符串。

所以给出你的例子：

Text file X contents: "The quick brown fox jumps over the lazy dog"
                       0   1     2     3   4     5    6   7    8

Text file Y contents: "Now is the time for all good men"
                       0   1  2   3    4   5   6    7

你会得到：

WordId | FileId | Position
the    | X      | 100001
the    | Y      | 001
quick  | X      | 01
is     | Y      | 01
....

（请注意，该位置也可以存储为实际位掩码以节省空间，但我不确定这在使用或更新值时是否会出现问题）

这个技巧是基于所谓的“拉什莫尔索引”，顺便说一句。

现在要查看文件“X”中“the”和“quick”之间的距离，您必须读取这两行并计算“is”实例和“the”实例之间的零数。请注意，您还可以添加额外的信息，例如“文件中单词的出现次数，以使实际距离匹配更容易：

WordId | FileId | Position |Occ
the    | X      | 100001   | 2
the    | Y      | 000001   | 1 
quick  | X      | 01       | 1
is     | Y      | 01       | 1
....

在这种情况下，您立即知道“the”在文件 X 中出现了两次，而“quick”只出现了一次。这可能有助于构建距离计数例程。

于 2012-07-11T07:02:54.970 回答
0

数据库对于您正在做的事情来说太过分了。您是否考虑过使用NoSQL 之类的东西或更轻量级的东西？而且您可能应该创建一些在后台更新索引的工作线程，而不是让很多线程更新它。这样可以减少争吵...

于 2012-07-11T22:02:47.090 回答
0

注释搞砸了代码格式，所以这里是：

我将上面的帖子标记为答案，因为这是我设计的解决方案的核心。我将位置和单词 ID 存储在一个 xml 列中，唯一的单词被规范化到一个单独的查找表中。搜索时，我执行类似于此的 XPath 查询：

m.WordIndex.query('
    let $dummy := 0
    return
        <word_list>
        {
            for $w in /wi/w
                where $w/@wid=1
                return <word wid="1" pos="{data($w/p)}"/>
        }
        </word_list>
    ') as WordPosition
于 2012-07-19T18:39:54.993 回答
0

假设您的纯文本文档仅包含索引词（即没有未索引的部分，例如标点符号，或者您满足于在索引中包含标点符号），也许以下想法值得一试：

在此处输入图像描述

如您所见，没有单独的“文档”内容。“文档”和“索引”是一回事，并且可以通过以正确的顺序遍历 DOCUMENT_WORD 并从 WORD 中查找 WORD_TEXT 来动态重建文档。

这个模型有几个很好的属性：

  • 文档和索引之间的数据不重复，节省空间。
  • 多个文档可以共享同一个单词 - 单词文本将只存储一次，从而节省空间。这实际上是一种字典压缩形式。
  • DOCUMENT_WORD 是一个很好的聚类候选者，因此同一文档的所有单词都存储在物理上接近，这应该在文档重建期间最小化 I/O。
  • 通过一点 JOINing，您可以在两个方向上进行查询，或者：“获取给定位置上（或附近）的单词”，或者：“获取给定单词的位置”。

顺便说一句，如果您决定切换到 Oracle，您可以将前沿索引压缩与 DOCUMENT_WORD 上的集群结合使用，以消除 DOCUMENT_ID 的重复并节省更多空间。您也许可以使用 SQL Server 的页面压缩来达到类似的效果。

于 2012-07-12T17:39:22.590 回答