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

Question

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

Я думаю о trie, но есть ли доступная версия trie для open source?

Спасибо

- Обновлен -

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

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

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

Слово1 Frequency1 Слово2 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, и вы должны знать источник, который вы, вероятно, следует пойти на формат что-то вроде:

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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

Answer 6

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

Answer 7

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

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

Answer 8

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

В 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 9

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