Как искать имя человека в тексте? (эвристический)

У меня есть огромный список полных имен людей, которые я должен искать в огромном тексте.

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

Пример:

В моем списке есть «Барак Хусейн Обама», поэтому я должен проверить, не встречается ли это имя в следующих текстах:

  • ... Кандидат Барак Обама был избран президентом США ... (неполно)
  • ... Кандидат Барак Хусейн был избран президентом Соединенных Штатов ... (неполно)
  • ... Кандидат Барак Х. О. был избран президентом Соединенных Штатов ... (сокращенно)
  • ... Кандидат Барак ОбаНа был избран президентом Соединенных Штатов ... (с ошибкой)
  • ... Кандидат Барак Овама был избран президентом Соединенных Штатов ... (неправильно введено, B стоит рядом с V)
  • ... Кандидат Джон Маккейн проиграл выборы ... (имя Обамы не встречается)

Конечно, для этого нет детерминированного решения, но ...

Что является хорошей эвристикой для такого поиска?

Если бы вам пришлось, как бы вы это сделали?


search language-agnostic heuristics
person Daniel Silveira    schedule 03.12.2008    source источник
comment
Не могли бы вы определить огромный текст размером 10 12 байт, 10 15 байт и более? Какие ресурсы доступны (компьютерное время, мощность)?   -  person jfs    schedule 04.12.2008
comment
Документ PDF с 200 страницами + с мелким шрифтом .... посчитайте!   -  person Daniel Silveira    schedule 04.12.2008
comment
$ pdftotext file.pdf - | wc --chars   -  person jfs    schedule 04.12.2008

Ответы (8)


arrow_upward
6
arrow_downward

Вы сказали, что это около 200 страниц.

Разделите его на 200 одностраничных PDF-файлов.

Поместите каждую страницу в «Механический турок» вместе со списком имен. Предложите вознаграждение в размере около 5 долларов за страницу.

person Joel Spolsky    schedule 23.12.2008
comment
5 долларов или 0,05 доллара? 1000 долларов могут быть непомерно высокими - person John Sheehan; 23.12.2008
comment
У Джоэла много стажеров, которых нужно кормить - эти стулья Aeron сами за себя не окупаются! - person Martin Beckett; 24.12.2008
comment
По сравнению со стоимостью написания кода для этого 1000 долларов кажется выгодной сделкой. Но я подозреваю, что вы, вероятно, могли бы заставить Mechanical Turks искать страницу по именам примерно за 0,50 доллара .... попробуйте один или два, это должно быть легко! - person Joel Spolsky; 24.12.2008

arrow_upward
5
arrow_downward

Разделите все на пробелы, удалив специальные символы (запятые, точки и т. Д.). Затем используйте что-нибудь вроде soundex для обработки орфографических ошибок. Или вы можете использовать что-то вроде lucene, если вам нужно искать много документов.

person joegtp    schedule 03.12.2008
comment
Мне нравится идея soundex для обработки орфографических ошибок. Вероятно, это не будет работать очень быстро для огромных списков, но все же это интересная идея. - person Bill the Lizard; 04.12.2008
comment
Если вы используете MSSQL, есть две готовые к использованию sql-функции SOUNDEX и DIFFERENCE. - person Stefan; 04.12.2008
comment
SOUNDEX хорошо работает с неанглийскими языками? В моем случае это португальский-BR - person Daniel Silveira; 04.12.2008
comment
@ Daniel, посмотрите здесь: stackoverflow.com/questions/299949/ Создать собственную версию soundex, чтобы вы могли сделать это самостоятельно, не так уж и сложно. - person Stefan; 04.12.2008
comment
Посмотрите, как работает soundex: ancestry.com/learn/library/article. aspx? article = 2253 - person Stefan; 04.12.2008
comment
В случае орфографических ошибок или неправильно написанных слов я думаю о расстоянии Левенштейна (en.wikipedia.org/wiki/Levenshtein_distance) .... Но как проверить неполные имена? - person Daniel Silveira; 04.12.2008

arrow_upward
2
arrow_downward

Вам нужна библиотека обработки естественного языка. Вы пытаетесь выделить подмножество собственных существительных. Если имена являются основным источником имен собственных, то это будет легко, если будет смешано приличное количество других имен собственных, это будет сложнее. Если вы пишете на JAVA, посмотрите OpenNLP или C # SharpNLP. После извлечения всех имен собственных вы, вероятно, могли бы использовать Wordnet для удаления большинства существительных, не являющихся именами. Вы можете использовать wordnet для идентификации частей имен, таких как «John», а затем искать соседние токены, чтобы подобрать другие части имени. У вас будут проблемы с чем-то вроде "John Smith Industries". Вам нужно будет посмотреть на свои базовые данные, чтобы увидеть, есть ли функции, которыми вы можете воспользоваться, чтобы помочь сузить проблему.

Использование НЛП - единственная надежная техника, которую я видел для решения подобных проблем. У вас все еще могут быть проблемы, поскольку 200 страниц на самом деле довольно мало. В идеале у вас должно быть больше текста и возможность использовать больше статистических методов для устранения неоднозначности между именами и не именами.

person Steve Severance    schedule 20.12.2008

arrow_upward
1
arrow_downward

На первый взгляд, я выбираю сервер индексации. lucene, FAST или Microsoft Indexing Server.

person Dan Blair    schedule 03.12.2008

arrow_upward
1
arrow_downward

Я бы использовал C # и LINQ. Я бы размечал все слова в пространстве, а затем использовал LINQ для сортировки текста (и, возможно, использовал функцию Distinct ()), чтобы изолировать весь интересующий меня текст. При манипулировании текстом я отслеживал индексы (что вы можете сделать с LINQ), чтобы я мог переместить текст в исходном документе - если это необходимо.

person Guy    schedule 24.12.2008

arrow_upward
0
arrow_downward

Лучший способ, который я могу придумать, - это определить грамматики в Python NLTK. Однако это может быть довольно сложно для того, что вы хотите.

Я бы лично использовал регулярные выражения при создании списка перестановок с некоторым программированием.

person Eric    schedule 03.12.2008

arrow_upward
0
arrow_downward

И SQL Server, и Oracle имеет встроенные функции SOUNDEX.

Кроме того, для SQL Server есть встроенная функция DIFFERENCE, которую можно использовать.

person Brian Schmitt    schedule 03.12.2008

arrow_upward
-1
arrow_downward

чистые старые сценарии регулярных выражений сделают свою работу.

используйте Ruby, это довольно быстро. читать строки и сопоставлять слова.

ваше здоровье

person cnikolaou    schedule 03.12.2008