Эффективный поиск в корпусе

Question

У меня есть несколько миллионов слов, которые я хочу найти в корпусе миллиардов слов. Какой будет эффективный способ сделать это.

Я думаю о trie, но есть ли реализация trie с открытым исходным кодом?

Спасибо

- Обновлено -

Позвольте мне добавить еще несколько деталей о том, что именно требуется.

У нас есть система, в которой мы сканировали источники новостей и получали популярные слова, основываясь на их частоте. Там может быть миллион слов.

Наши данные будут выглядеть примерно так.

Word1 Frequency1 Word2 Frequency2 (Табуляция с разделителями)

Мы также получили самые популярные слова (1 миллиард) из другого источника, который также содержит данные в вышеуказанном формате.

Вот что я хотел бы получить в качестве вывода.

• Слова, общие для обоих источников
• Слова присутствуют только в нашем источнике, но не в справочном.
• Слова, присутствующие только в справочном источнике, но не в нашем источнике.

Я могу использовать comm (команда bash) для вышеуказанной информации только для слов. Я не знаю, как использовать comm для сравнения только с одним столбцом, а не с обоими.

Система должна быть масштабируемой, и мы хотели бы выполнять это каждый день и сравнивать результаты. Я также хотел бы получить приблизительные совпадения.

Итак, я думаю о том, чтобы написать работу по сокращению карты. Я планирую написать карту и уменьшить функциональность, как показано ниже, но у меня мало вопросов.

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.

У меня есть два вопроса. В карте уменьшить, я могу дать в качестве входных данных каталог, содержащий мои два файла. Я не знаю, как получить имя файла, из которого я читаю слова. Как получить эту информацию? Как можно записывать в разные выходные файлы, потому что при уменьшении фазы автоматически записывается только файл по умолчанию, называемый part-xxxxx. Как записать в разные выходные файлы.

Спасибо, что прочитали это.

Answer 1

С MapReduce вы не должны пытаться делать все за один шаг или работу. Похоже, вы должны разбить эту проблему на несколько этапов. Поскольку вы генерируете данные, хранящиеся в HDFS, и вам необходимо знать источник, вам, вероятно, следует перейти к формату, например:

{ИСТОЧНИК}, {СЛОВО}, {} ЧАСТОТЫ

Помните, что вы говорите о распределенной файловой системе, поэтому упоминание ваших входных данных как file1 и file2 технически неверно. И ваши справочные данные, и исходные данные будут распределены по всему кластеру, причем фрагменты каждого будут расположены на каждом узле.

Далее, начиная с примера с псевдокодом, вам нужно создать задание, которое соотносит слово с источником и его частотой. Ваш маппер будет работать просто отлично, но для сокращения нужно будет связать слова с источниками. Вам нужно будет создать свой собственный записываемый объект, который содержит карту <источник, частота>. Это будет выводиться на HDFS как промежуточные данные, с которыми могут работать ваши последующие задания фильтра.

Затем вы можете использовать выходные данные этого шага в качестве входных данных для 3 различных заданий MapReduce. Где каждый ищет разные комбинации источников. Эти задания будут очень простыми, поскольку маппер будет просто проходить через одни и те же данные, но редуктор будет проверять каждое значение для различных комбинаций источников.

Так что, если вы выберете такой подход, вам понадобится 4 задания MapReduce. Вам не нужно запускать каждую из них вручную, у вас может быть одно задание, которое запускает каждое задание последовательно. В качестве альтернативы, поскольку последние 3 задания будут использовать одни и те же входные данные, вы можете запустить эти три одновременно, как только закончится первое. Вероятно, это будет зависеть от объема данных и промежуточных данных, которыми может управлять ваш кластер, а также от числа картографических / редукторных функций, необходимых для каждого задания.

Надеюсь, это предложение поможет.

Answer 2

В духе быстрого и грязного:

fgrep --mmap -f query-file corpus-file

Answer 3

Это похоже на работу, для которой был разработан алгоритм поиска строки Aho-Corasick . Я никогда не кодировал это сам, но немного погуглив, надо немного кодировать.

Рабин-Карп также может работать, но я понятия не имею, как это работает для нескольких паттернов, когда они не все одинаковой длины. Примечание: псевдокод из нескольких паттернов в статье в Википедии выглядит неправильно. Но должен дать вам отправную точку.

Answer 4

Поскольку вы можете использовать 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"))

Answer 5

Настольный ПК может сделать это. Меньший набор данных поместится в памяти, и это все, что вам нужно.

В 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")

Кластер может сделать это быстрее. Но вы можете попробовать это дома.

Answer 6

tokenizer.c, скомпилированный в a.out, может токенизировать корпус, а затем использовать сценарий оболочки systemclose для эффективной работы

 ./a.out <
/live/memory/var/cache/man/whatis  | sort | awk {'print $1'} | uniq -c
| sort -rn > file.txt

Answer 7

Я не уверен насчет его производительности, но Python nltk был разработан для такого рода вещей: для токенизации больших текстовых корпусов и сравнения между ними. Книга «Обработка естественного языка с Python» использует этот инструментарий и имеет много примеров. Он доступен онлайн бесплатно.

Answer 8

Структура данных, используемая в текстовых поисковых системах, называется инвертированный индекс . И, как уже было сказано, очень хорошая поисковая система с открытым исходным кодом - Lucene .

Answer 9

Если бы я делал это на Java, я бы использовал HashMap. Википедия предполагает, что в некоторых случаях три незначительно лучше, но я не уверен, что вы увидите большую разницу.