Указатель предложений - PullRequest
       1

Указатель предложений

1 голос
/ 07 сентября 2011

У меня есть несколько десятков тысяч коротких документов, каждый из которых содержит от 10 до 20 предложений на английском языке (а также некоторые другие не-предложения, такие как, возможно, форматирование HTML или другой «мусор»).Эти документы вырезаны из других более длинных документов - другими словами, более короткий документ «А1» может быть предложением с 10 по 20 оригинального документа «А», а другой более короткий документ «А2» может быть предложением с 11 по 25 оригинального документа того же документа.«А», а некоторые из исходных исходных документов могут представлять собой резюме или копии других исходных исходных документов, так что в исходном исходном документе «В» могут также содержаться предложения с 10 по 20 оригинального исходного документа «А», хотя это необязательно вто же местоИ эта же группа предложений могла быть извлечена из «B» в другой короткий документ «B3».

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

Я думаю, что мне нужен какой-то код для создания эффективного хеш-кода для предложения, у которого очень низкая вероятность создания одного и того же хэш-кода для двух разных предложений.Является ли алгоритм хеширования, используемый в Java, String.hashCode () хорошим выбором для этого?MD5 или другой криптографический хэш кажется слишком дорогим и излишним для этой цели.

Ответы [ 2 ]

5 голосов
/ 07 сентября 2011

Я недавно оценил алгоритмы хеширования с требованием, чтобы на нескольких миллионах входов не было практически никакой возможности столкновения хэшей, и хеширование должно быть очень быстрым. CityHash стал победителем, победителем.

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

https://sites.google.com/site/craigandera/craigs-stuff/odds-ends/the-birthday-problem-calculator

1 голос
/ 07 сентября 2011

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...