Хранение текста в полу-доступном для поиска, но компактном формате

Question

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

Это заставило меня задуматься о том, как другие крупные текстовые системы, такие как WordNET или поисковые системы, справляются с этой проблемой. Интересно, есть ли способ нормализовать данные, но все же включить его в формат для поиска?

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

TABLE Words
{
    id
    word
}

TABLE TWOGRAM
{
    first_word_id
    second_word_id
}

TABLE THREEGRAM
{
    first_word_id
    second_word_id
    third_word_id
}

TABLE FOURGRAM
{
    first_word_id
    second_word_id
    third_word_id
    forth_word_id
}

Есть ли более эффективный способ компактного хранения всех этих данных?

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

Answer 1

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

[Edit] С более подробной информацией, как и было запрошено: Целью здесь является обработка небольших сжатых блоков данных, поэтому необходимо поддерживать требования к памяти на разумном уровне. «Разумный» зависит от вашей целевой системы, поэтому может быть 256 строк, или 2K, или 8K.

Однако в каждой строке есть несколько полей. Таким образом, сжатие напрямую не принесет значительной экономии (например, zip равен «только» x5). К счастью, символ разделения между этими полями хорошо известен (0x09), поэтому можно получить начало и конец каждого поля.

Идея состоит в том, чтобы сгруппировать все «Поля 1» вместе, затем «Поля 2», затем «Поля 3» и так далее. Если блок, извлеченный из файла .csv, содержит 2 тыс. Строк, мы знаем, что у нас есть 2 тыс. Полей каждого типа.

Тогда простой алгоритм быстрого сжатия сотворит чудеса с этой преобразованной структурой. Корреляции очень сильны, так как последовательные поля имеют много общего. Степень сжатия 10x не удивительна для таких данных. Наборы данных Google N-Gram, вероятно, будут еще более благоприятными.

Поскольку ваша цель - сохранить как можно больше данных в памяти для поиска в них, рекомендуется держать каждый блок достаточно маленьким (примерно между 256 и 8 КБ) и использовать очень быстрый алгоритм сжатия / распаковки. Таким образом, декомпрессия будет достаточно быстрой, чтобы стать незначительной частью вашего алгоритма. Например, что-то вроде LZ4 обеспечивает скорость декомпрессии около 1 ГБ / с.

По поводу поиска: все зависит от того, что вы хотите найти, но если речь идет о поиске точного N-грамма, то нам повезло, поскольку они уже отсортированы в лексикографическом порядке.

На этом этапе достаточно сохранить первый N-грамм каждого блока в таблицу. При поиске определенного N-грамма просто необходимо выяснить, в каком блоке он находится. Первый N-грамм блока обязательно <=. N грамм следующего блока обязательно>. Как показано выше, распаковка блока должна быть незначительной частью алгоритма.

Даже с блоками по 2K строк может потребоваться много «N-граммы заголовка» для хранения, поэтому простой поиск пузырьков может быть довольно долгим. Рекомендуется поиск по дереву или сводной таблице.

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

Answer 2

Вместо того, чтобы хранить 360 миллиардов 1грамм снова и снова для каждой пары или 2+ групп - Хранить слова один раз - и затем использовать меньшие целые числа для представления слов, кажется лучшим выбором.

(я суммировал свои оценки ниже.)

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

Статистика говорит нам, что средняя длина слова в английском языке составляет 5,1 символа.В вашем приложении это то же самое, что 5,1 байта.Средняя длина двух слов составляет около 10,2 байта;длина двух целых чисел составляет 8 байтов.

В файле 71 содержится около 66 миллионов 2грамм (выбранных случайным образом).При 10,2 байт на запись вы ищете около 673 мегабайт для этого файла.(Предполагается, что вы будете хранить только слова, а не количество.) Для 100-граммовых файлов вам потребуется от 52 до 67 гигабайт (без учета индексов).Добавьте 50% за наше глубокое невежество.100 концертов покроют 2граммы.

Если вы сохраняете счет со словами, этот файл составляет 1,6 гигабайта, и 100 из них должны составлять около 160 гигабайт.Таким образом, у нас есть диапазон от 100 до 160 гигабайт для хранения 2-х грамм.

Я оставлю оценку пространства, требуемого для индексов, вам.

Целые числа экономят 2,2 байта на слово.Но хранение двух целых чисел означает, что вам всегда нужно делать два объединения, чтобы получить реальные данные обратно.(Хранение пяти целых чисел для 5грамм означает, что вам понадобится пять объединений и получите реальные данные обратно.) Сохранение самих слов не требует объединения для получения реальных данных.

Если вы также храните счетчики, вы можете сэкономить место, сохранив внешний ключ для ngram вместо использования отдельных слов.Таким образом, вы можете хранить

ngram_id  ngram_text
--
143564    five pounds

в одной таблице и

ngram_id    year    match_count  page_count  volume_count 
--
143564      1999    4            3           3
143564      2000    2            2           1
143564      2001    1            1           1
143564      2002    1            1           1
143564      2003    2            2           2
143564      2004    1            1           1
143564      2005    6            6           5
143564      2006    30           21          17
143564      2007    39           37          26
143564      2008    44           41          28

в другой.

Для этого конкретного 2 грамма текст занимает 11 байтов, а целое -4. Экономия 7 байтов в каждом из 10 рядов, 70 байтов.Требуется одно присоединение для получения реальных данных.Для этого подхода я бы оценил около 130 гигабайт для всех 2-грамм, за исключением индексов и таблицы, которая предоставляет внешние ключи.

Сводка моих оценок пространства, необходимого для хранения 2-х грамм, на основе 100 файлов из 66 миллионовстрок.Исключая пространство для индексов и общих накладных расходов на хранение (которые, в зависимости от dbms, могут быть существенными.)

                           row_len  gigabytes  joins
----------------------------------------------------
words        with counts     163.2      1,077      0
two integers with counts     128.0        845    2-5

words        without counts   10.2         67      0
two integers without counts    8           53    2-5

one integer  with counts      20          132      1
one integer  without counts    4           26 (for completeness, but not really useful)

Многотерабайтные дисковые массивы в наши дни не слишком дороги.Вы собираетесь зарабатывать на этом?