4

我有几百万个单词，我想在十亿个单词的语料库中搜索。什么是有效的方法来做到这一点。

我正在考虑使用 trie，但是是否有可用的 trie 开源实现？

谢谢

- 更新 -

让我添加一些关于究竟需要什么的更多细节。

我们有一个系统，我们抓取新闻来源并根据词的频率获取流行词。可能有一百万个单词。

我们的数据看起来像这样。

字 1 频率 1 字 2 频率 2（制表符分隔）

我们还从另一个来源获得了最受欢迎的词（10 亿），其中也包含上述格式的数据。

这是我想得到的输出。

  • 两个来源共有的词
  • 单词仅出现在我们的来源中，但不在参考来源中。
  • 单词仅出现在参考来源中，但不在我们的来源中。

我只能对上述信息使用 comm（bash 命令）来获取单词。我不知道如何使用 comm 仅与一列而不是两列进行比较。

该系统应该是可扩展的，我们希望每天都执行此操作并比较结果。我也想得到近似匹配。

所以，我正在考虑写一个地图减少工作。我打算编写如下的 map 和 reduce 函数，但我有几个问题。

Map
For each word
output key = word and value = structure{ filename,frequency}
done

Reduce
For each key
Iterate through all the values and check if both file1 and file2 are contained.
If yes, then write it to appropriate file.
If only in file1, write it to file1only file
If only in file2, write it to file2only file.
Done.

我有两个问题。在 map reduce 中，我可以提供一个包含我的两个文件的目录作为输入。我不知道如何获取我从中读取单词的文件名。如何获取这些信息？如何写入不同的输出文件，因为 reduce 阶段会自动写入名为 part-xxxxx 的默认文件。如何写入不同的输出文件。

感谢您阅读本文。

4

9 回答 9

2

使用 MapReduce，您不应该尝试在一个步骤或工作中完成所有事情。看起来您应该将此问题拆分为多个步骤。由于您正在生成存储在 HDFS 上的数据，并且您需要知道来源，您可能应该采用如下格式：

{SOURCE},{WORD},{FREQUENCY}

请记住，您正在谈论分布式文件系统，因此将您的输入称为 file1 和 file2 在技术上是不正确的。您的参考数据和源数据都将分布在整个集群中，每个数据块都位于每个节点上。

接下来，从您的伪代码示例开始，您将需要创建一个将单词与源及其频率相关联的作业。您的映射器可以正常工作，但 reduce 需要将单词链接到源。您需要创建自己的 Writable 对象，其中包含 Map<source, frequency>。这将作为后续过滤作业可以使用的中间数据输出到 HDFS。

然后，您可以将此步骤的输出用作 3 个不同 MapReduce 作业的输入。每个人都在寻找不同的来源组合。这些作业将非常简单，因为映射器只会传递相同的数据，但化简器将检查每个值的不同来源组合。

因此，如果您采用这种方法，您将需要 4 个 MapReduce 作业。您不需要手动运行每个作业，您可以拥有一个按顺序运行每个作业的作业。或者，由于最后 3 个作业将使用相同的输入数据，因此您可以在第一个作业完成后同时启动这三个作业。这可能取决于您的集群能够管理的数据量和中间数据量，以及每个作业需要的映射器/缩减器的数量。

希望这个建议有所帮助。

于 2010-01-25T23:54:52.137 回答
1

这看起来像是为Aho-Corasick字符串搜索算法设计的工作。我自己从来没有编写过代码，但是谷歌搜索一下应该会出现一些代码。

Rabin-Karp也可能有效，但我不知道当它们的长度不同时它如何适用于多个模式。注意：维基百科文章中的多模式伪代码似乎是错误的。但应该给你一个起点。

于 2010-01-24T22:49:10.170 回答
1

本着快速和肮脏的精神：

fgrep --mmap -f query-file corpus-file
于 2010-01-25T01:03:56.280 回答
0

台式电脑可以做到这一点。较小的数据集将适合内存，这就是您所需要的。

在 Python 中：

# Load the words from the small file into one big hash set
small_set = set(line.split()[0] for line in open("small.txt", "r"))

# Open 3 output files.
f1 = open("common.txt", "w")
f2 = open("large_only.txt", "w")
f3 = open("small_only.txt", "w")

# Find all words in the large set that aren't in the small set.
for line in open("large.txt", "r"):
    word = line.split()[0]
    if word in small_set:
        f1.write(line)  # word is in both sets
        small_set.remove(word)
    else:
        f2.write(line)  # word is in large but not small

# Everything left over in small_set wasn't in the large_set.
for word in small_set:
    f3.write(word + "\n")

集群可以更快地做到这一点。但是你可以在家里试试这个。

于 2010-01-28T22:40:44.067 回答
0

文本搜索引擎中使用的数据结构称为倒排索引。正如已经说过的，非常好的开源搜索引擎是Lucene。

于 2010-01-25T14:46:35.143 回答
0

如果我在 Java 中执行此操作，我会使用 HashMap。Wikipedia建议在某些情况下 trie 稍微好一些，但我不确定你会看到多大的不同。

于 2010-01-24T22:40:50.900 回答
0

我不确定它的性能，但 Python 的nltk旨在做这种事情：标记大型文本语料库并允许您在它们之间进行比较。“Natural Language Processing with Python”一书使用了这个工具包，并有很多例子。它可以免费在线获得。

于 2010-01-26T00:03:07.623 回答
0

既然你可以使用comm，我想你一定已经对输入文件进行了排序。

这是一个类似的程序comm，它只查看第一列，但生成包含整行输入的输出。仅当输入已排序时才有效！

这是一个完整的程序。您所要做的就是将它放在一个文本文件中并从命令行运行它。

#!/usr/bin/env python
#
# comm.py - Compare 2 sorted files line by line, based on the first column.
# Usage:   python compare.py FILE1 FILE2 OUTFILE1 OUTFILE2 OUTFILE12
# OUTFILE1 receives all entries that are only in FILE1, etc.

import sys

def compare(f1, f2, out1, out2, out12):
    def get(f):
        line = f.readline()
        if line == '':
            return None
        first, rest = line.rstrip('\n').split('\t', 1)
        return first, rest, line

    e1 = get(f1)
    e2 = get(f2)
    while e1 and e2:
        if e1[0] == e2[0]:   # common entry
            out12.write(e1[0] + "\t" + e1[1] + "\t" + e2[1] + "\n")
            e1 = get(f1)
            e2 = get(f2)
        elif e1[0] < e2[0]:  # e1 is not in f2
            out1.write(e1[2])
            e1 = get(f1)
        else:                # e2 is not in f1
            out2.write(e2[2])
            e2 = get(f2)
    if e1:
        buf = e1[2]
        while buf:
            out1.write(buf)
            buf = f1.read(8192)
    if e2:
        buf = e2[2]
        while buf:
            out2.write(buf)
            buf = f2.read(8192)

compare(open(sys.argv[1], "r"),
        open(sys.argv[2], "r"),
        open(sys.argv[3], "w"),
        open(sys.argv[4], "w"),
        open(sys.argv[5], "w"))
于 2010-01-29T17:03:09.323 回答
0

编译为 a.out 的 tokenizer.c 可以对语料库进行标记，然后使用 systemclose shell 脚本来提高性能

 ./a.out <
/live/memory/var/cache/man/whatis  | sort | awk {'print $1'} | uniq -c
| sort -rn > file.txt
于 2010-01-26T00:10:16.797 回答