Как подсчитать каждое вхождение биграммы в крупном текстовом корпусе

Question

У меня большой объем текста, который включает статьи в Википедии, новостные статьи и т. Д. Всего около 1,5 миллиарда слов и около 3 миллионов уникальных слов.

Что я хочу сделать, так это решить, когда считать последовательные слова одним словом, например, «апельсиновый сок», вероятно, следует рассматривать как одно слово. Чтобы решить, следует ли рассматривать пару слов как одно слово, мне нужно знать, сколько раз встречается биграмма и сколько раз встречается каждое из слов в биграмме. bigramCount/(word1Count*word2Count) > threshold Проблема в том, что переменная, содержащая все числа биграмм в моем тексте, заняла бы больше памяти, чем размер памяти моего компьютера.

То, что я пытался сделать, это:

1. Count single words
2. For every single word:
    1. Count every ocurrence of a bigram that starts with that word
    2. Decide, applying the formula, which of those bigrams should be treated as a single word.

Таким образом, память становится проще, но это занимает слишком много времени. В настоящее время я делаю это, но он работает по крайней мере один день, поэтому я пытаюсь найти лучший способ сделать это.

Есть идеи?

Answer 1

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

Сначала создайте два файла, один для отдельных слов, а другой для биграмм.

Теперь, просмотрите ваш текст последовательно. Когда вы читаете каждое слово, выведите его в файл с одним словом. Объедините его с предыдущим словом и запишите пару в файл биграмм. Например, учитывая предложение «смысл в том, что нет смысла делать весь разговор бессмысленным», файл с одним словом будет содержать одно слово в строке. Файл биграммы будет содержать:

the point
point is
is that
that there
there is
...

Теперь, используя утилиту сортировки, предоставленную вашей операционной системой, сортируйте каждый файл. Это группирует идентичные слова вместе.

Затем напишите программу, которая читает файл построчно, считая идентичные строки. Получив общее количество слов, напишите соответствующий файл, содержащий word,count. Так что если у вас есть:

apple
apple
banana
cherry
cherry
cherry

Тогда ваш вывод будет:

apple,2
banana,1
cherry,3

Сделайте то же самое с файлом биграмм.

Наконец, загрузите файл с одним словом в карту или словарь, проиндексированный по слову со значением, равным количеству. Три миллиона уникальных слов должны соответствовать. Если нет, вы можете поместить их в базу данных. Что-то вроде SQLite будет работать очень хорошо.

Тогда начните читать ваш файл биграммы. Каждая строка содержит биграмму и ее количество. Затем вы можете выполнить расчет и принять решение, хотите ли вы рассматривать его как одно слово, или вы можете вывести биграм с его счетом и счетом в отдельный файл и принять решение позже.

Вы можете уменьшить размер промежуточных файлов, созданных при первом проходе, сохранив некоторые данные в памяти. Вместо того, чтобы сразу записывать каждое слово и биграмму в промежуточный файл, сохраните в памяти два словаря и ограничьте их размер. Когда словарь заполнится, запишите слова и цифры на диск и очистите словарь. Таким образом, вместо сотен тысяч отдельных слов «the» в файле вы получите всего несколько «100000» записей.

Уменьшение размера промежуточных файлов увеличит скорость сортировки. На втором шаге, когда вы удаляете дубликаты, вы добавляете счетчики для каждой записи, а не просто добавляете один для каждой записи.

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

Еще одним преимуществом является то, что это решение является достаточно масштабируемым. Я сделал что-то очень похожее на своем ноутбуке (8 ГБ памяти), выполняя подсчеты слов и биграмм против загрузки всей английской Википедии. Это заняло некоторое время (несколько часов), но сработало хорошо.

Answer 2

Разбейте ваши данные на куски равномерного размера 100-200 МБ. Запустите свой алгоритм. Сохраните запятую 85% (наиболее часто встречающихся комбинаций) биграмм, разделенных в файле (1.csv). Сортировать файл по первому слову.

Повторяйте для разных файлов (2,3,4 ...), пока нет больше данных.

Соотнесите (объедините одинаковое количество значений) для файлов 1 и 2 в новый CSV-файл 1a. Соотнесите файлы 3 и 4 в новый файл CSV 2a. Повторите для остальных файлов. Если существует нечетное количество файлов, сопоставьте последний файл со случайным файлом 1..n) Затем сопоставьте файлы 1a, 2a ..

Продолжайте, пока не будет единого файла с вашими результатами.

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

Наиболее полное решение - полностью агрегировать расширение всех уровней. Например, (Подбор 1 и 3 => 1b, 1 и 4 => 1c ... 2 и 1 => 2b, 2 и 3 => 2c, 2 и 4 => 2d ...) ... и затем на следующем шаге объедините 1a и 1b ..., 2a и 2b ... Это экспоненциальное решение (медленно).

Чтобы сбалансировать производительность И для уменьшения сложности и уменьшения смещения, вы можете рандомизировать пары на более низких уровнях:

Например: рандомизировать порядок чанков по мере их анализа на каждом уровне. Убедитесь, что алгоритм выводит каждую пару только один раз.

Если вы рандомизируете выборки в нижней части дерева несколько раз (примерно 1/2 от полного раскрытия, как описано выше), при этом удаляя дублирующиеся пары из всех предыдущих итераций, результирующая точность значительно улучшается в вышеуказанных слоях .

Если вы повторите эту рандомизацию для второго и третьего уровней (если полный анализ по-прежнему невозможен) за пределами третьего уровня, значительное повышение производительности вряд ли возможно из-за закона убывающей доходности.

Я бы рекомендовал использовать предварительно созданную базу данных биграмм или, по крайней мере, ограничить на верхнем уровне кандидатов в биграммы (существительное | прилагательное, существительное). В противном случае вы можете получить наиболее употребительную комбинацию существительное / глагол (в большинстве других современных наборов данных американского английского языка это будет «Я есть» или «У меня есть»).