Как я могу проанализировать свободный текст (твиты Twitter) с большой базой данных значений?

Question

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

«Сегодня я спустился в лес и не поверил своим глазам: я увидел гигантского белого медведя на пикнике с красной белкой».

... Я хотел бы отметить фразы «гигантский белый медведь» и «красная белка», как они появляются в моей базе данных.

Это кажется мне проблемой, которая, вероятно, решалась много раз, но с того места, где я сижу, это выглядит непомерно интенсивно - итерации по каждой записи в БД, проверка соответствия в строке, безусловно, является безумным способом сделать это.

Может ли кто-нибудь, имеющий ученую степень, избавить меня от моих страданий? Я работаю в C #, если это имеет какое-либо значение. Ура!

Answer 1

Предполагая, что база данных довольно статична, используйте фильтр bloom . Это вырожденная форма хеш-таблицы, в которой хранятся только биты, указывающие на наличие значения, без сохранения самого значения. Это вероятностный случай, поскольку хэши могут сталкиваться, поэтому для каждого попадания потребуется полный поиск. Но фильтр блума 1 МБ с 500 000 записей может иметь всего 0,03% ложных срабатываний.

Немного математики: Для получения этой низкой скорости требуется до 23 хэш-кодов, каждый из которых имеет 23 бита энтропии, в общей сложности 529 бит. 64-битная хеш-функция Боба Дженкинса генерирует 192 бита энтропии за один проход (если вы используете незарегистрированные переменные в hash(), которые Боб называет «ОК», как «посредственный» хеш) требуется максимум три прохода. Из-за того, как работают фильтры Блума, вам не нужна вся энтропия в каждом запросе, так как большинство поисков сообщит о пропусках задолго до того, как перейти к 23-му хэш-коду.

РЕДАКТИРОВАТЬ: Вам, очевидно, придется разбирать слова из текста. Поиск каждого экземпляра /\b\w+\b/, вероятно, подойдет для первой версии.

Чтобы сопоставить фразы, вам нужно будет проверить каждую подпоследовательность n -слов (aka n -грамм), где n - это каждое число от 2 до самой большой фразы в вашем словаре. Вы можете сделать это намного дешевле, добавив любое слово, которое появляется в фразе, в отдельный фильтр Блума и протестировав n -грамм, для которых каждое слово проходит этот второй фильтр.

Answer 2

Вы пытались создать три для своего словаря? Если вы разделите твит на куски и сопоставите каждый кусочек с деревом, вы получите линейную сложность.

Answer 3

Что не так с Regex? =) Это подходит для небольших текстовых поисков.

string input = @"I went down to the woods to day and couldn't believe my eyes: I saw a bear having a picnic with a squirrel. I am a human though!";
Regex animalFilter = new Regex(@"\b(bear|squirrel|tiger|human)\b");
foreach (Match s in animalFilter.Matches(input))
{
    textBox1.Text += s.Value + Environment.NewLine;
}

Дает вывод:

медведь
Белка
человек

Еще немного:

string input = @"I went down to the woods to day and couldn't believe my eyes: I saw a bear having a picnic with a squirrel. I am a human though!";
Regex animalFilter = new Regex(@"\b(bear|squirrel|tiger|human)\b");

Dictionary<string, int> animals = new Dictionary<string, int>();

foreach (Match s in animalFilter.Matches(input))
{
    int ctr = 1;
    if (animals.ContainsKey(s.Value))
    {
        ctr = animals[s.Value] + 1;
    }
    animals[s.Value] = ctr;
}
foreach (KeyValuePair<string,int> k in animals)
{
    textBox1.Text += k.Key + " ocurred " + k.Value + " times" + Environment.NewLine;
}

Результаты:

медведь произошел 1 раз
Белка произошла 1 раз
человек произошел 1 раз

Answer 4

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