Блог

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

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

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

 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
}
  

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

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

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

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

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

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

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

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

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

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

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

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

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

(Я обобщил свои оценки ниже.)

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

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

В файле с номером 71 содержится около 66 миллионов 2грамм (выбирается случайным образом). При 10,2 байтах на запись для этого файла требуется около 673 мегабайт. (Это предполагает, что вы собираетесь хранить только слова, а не количество.) Для 100 файлов объемом 2 грамма вам потребуется от 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
  

в другом.

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

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

                            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)
  

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