Нечеткие регулярные выражения - PullRequest
Новая
       1

Нечеткие регулярные выражения

28 голосов
/ 11 ноября 2010

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

В качестве примера я хочу сопоставить строку со словами «НовыйЙорк »предшествует 2-значное число.Трудность возникает из-за того, что текст взят из OCR PDF, поэтому я хочу сделать нечеткое совпадение.Я хотел бы сопоставить: 

12 New York
24 Hew York
33 New Yobk

и другие "близкие" совпадения (в смысле расстояния Левенштейна), но не: 

aa New York
11 Detroit

Очевидно, мне потребуетсяукажите допустимое расстояние («нечеткость») для совпадения.

Насколько я понимаю, я не могу использовать для этого модуль Perl String::Approx, потому что мне нужно включить обычныйвыражение в моем совпадении (чтобы соответствовать предыдущим цифрам).

Кроме того, я должен отметить, что это очень упрощенный пример того, что я действительно пытаюсь сопоставить, поэтому я не ищу грубуюСиловой подход.

Отредактировано, чтобы добавить:

Хорошо, мой первый пример был слишком прост.Я не хотел, чтобы люди зацикливались на предыдущих цифрах - извините за плохой пример.Вот лучший пример.Рассмотрим эту строку:

ASSIGNOR, BY MESHS ASSIGN1IBNTS, TO ALUSCHALME&S MANOTAC/rURINGCOMPANY, A COBPOBATlOH OF DELAY/ABE.

Что на самом деле это говорит:

ASSIGNOR, BY MESNE ASSIGNMENTS, TO ALLIS-CHALMERS MANUFACTURING COMPANY, A CORPORATION OF DELAWARE

Что мне нужно сделать, это извлечь фразу "ALUSCHALME & S MANOTAC / RURINGCOMPANY "и" DELAY / ABE ".(Я понимаю, что это может показаться безумием. Но я оптимист.) В общем, шаблон будет выглядеть примерно так:

/Assignor(, by mesne assignments,)? to (company name), a corporation of (state)/i

, где соответствие нечеткое.

Ответы [ 9 ]

17 голосов
/ 21 ноября 2010

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

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

Попробуй так:

  • превратит ваши тексты и шаблоны в сокращенный набор символов, например только в верхнем регистре , зачистку, словоизацию (один пробел между словами), все символы заменяются на "#" или что-то в этом роде.
  • выберите длину q-грамма для работы. Попробуйте 3 или 2. Мы называем это q=3.
  • than, создайте профиль qgram каждого текста:
  • разбить каждый текст на q-слова, т.е. NEW_YORK становится [NEW, EW_, W_Y, _YO, ORK], сохраняйте это вместе с каждым текстом.
  • если вы ищите ваш шаблон , то вы делаете то же самое с вашим шаблоном,
  • перебрать вашу базу данных text-qgram и
    • подсчитайте для каждой шаблона / текста -пары, сколько qgrams совпадают.
    • каждый удар увеличивает счет на 1.
  • тексты с наибольшим количеством баллов - ваши лучшие хиты .

Если вы сделали это, вы можете настроить этот алгоритм:

  • добавьте все ваши тексты (а также шаблон перед поиском) с q-1 специальными символами, так что даже ваши короткие слова получат достойный профиль. Например New York становится ^^NEW YORK$$.
  • Вы даже можете поиграть с заменой всех согласных на «x», а гласных на «o» и так далее. Поиграйте с парой классов персонажей таким образом или даже создайте суперсимволов , заменив группы персонажей друг на друга, то есть CK становится K или SCH становится $ .
  • при увеличении счета с помощью qgram-удара вы можете отрегулировать значение 1 другими способами, такими как разница в длине текст против шаблона .
  • храните 2 грамма и 3 грамма, и при подсчете весите тогда по-другому.

Обратите внимание, что этот алгоритм в описанной здесь базовой форме не имеет хорошего времени выполнения во время поиска, то есть O(|T|*|P|) (с |T| и |P| общей длиной ваших текста и рисунок * * 1 096). Это потому, что я описал, что вы перебираете все свои тексты, а затем над своим шаблоном . Поэтому это практично только для средних текстов -базы. Если вы потратите немного времени, вы можете создать расширенную структуру индекса поверх q-грамм (возможно, с использованием хеш-таблиц), так что это может быть полезно и для огромных текстов -баз.

3 голосов
/ 11 ноября 2010

Вы можете попробовать что-то вроде Web 1T 5-граммовая версия 1 и метод максимизации условного правдоподобия.

Если я правильно помню, глава 14 Красивые данные посвящена этому набору данных и его использованию для выявления орфографических ошибок и т. Д.

3 голосов
/ 11 ноября 2010

Разделите задачу на две части:

  1. Сопоставьте двузначное число.
  2. Нечетко сопоставьте остаток с «Нью-Йорк».

В примере вы знаете, что «Нью-Йорк» состоит из 2 слов;Вы могли бы использовать это, чтобы упростить устранение таких альтернатив, как «Детройт» (но не обязательно «Сан-Франциско»).

Возможно, вы даже сможете использовать ' String :: Approx в конце концов, хотя в нем упоминаются:

... модули Text :: Levenshtein и Text :: LevenshteinXS в CPAN.См. Также Text :: WagnerFischer и Text :: PhraseDistance.

(Мой Perl не смог найти Text :: PhraseDistance через CPAN - остальные доступны и установить ОК.)

3 голосов
/ 11 ноября 2010

У регулярных выражений есть определенные правила, они не созданы для того, чтобы делать то, что вы хотите. Будет гораздо проще сделать два прохода. Используйте регулярные выражения, чтобы убрать числа, а затем используйте модуль, чтобы закрыть ваш матч.

Примерно так (при условии, что вы вводите строки из файла) 

while( my $line = <$fh> ) {
    chomp $line;

    # do we have digits?
    if( $line =~ /^\d+/ ) {
         # removes spaces and digits from the beginning of the line
         $line =~ s/^[\d\s]*//g;

         # use your module to determine if you have a match in the remaining text.
         if( module_match ) {
             # do something
         }
         else {
             #no match
         }
    }
    else {
        # no match
    }
}
2 голосов
/ 19 ноября 2010

Рассматривали ли вы использование Jarkko's String :: Approx модуля на CPAN? В нем есть алгоритм agrep, но он намного медленнее, чем у Уди.

2 голосов
/ 15 ноября 2010

Основное правило: когда вам нужно перейти к переполнению стека и спросить: «Как я могу сделать X в одном регулярном выражении?»вам следует подумать о том, чтобы использовать X не только с одним регулярным выражением.

Исходя из ваших правок, я бы сделал что-то вроде этого: 

while(<>) {
  chomp;
  if(/assignor, by (\w+) (\w+), to (\w+), a (\w+) of (\w+)/i) {
    # now use String::Approx to check that $1, $2, $3, $4, and $5 match
  } else {
    warn "Errors!\n";
  }
}

Я не дам вам всего здесьЯ не сделал бит ", by (\w+) (\w+)" необязательным, чтобы упростить регулярное выражение, чтобы вы могли понять его суть.Для этого вам, вероятно, придется прибегнуть к именованным захватам и группе без захвата (?:).Мне не хотелось вникать во все это, я просто хотел помочь вам понять, как я буду к этому подходить.

Помните: если вам нужно спросить: «Как мне все это сделать в одном регулярном выражении?»вам следует перестать пытаться сделать все это в одном регулярном выражении.

2 голосов
/ 11 ноября 2010

Ну, вы можете сузить своих кандидатов с помощью Text::Levenshtein, чтобы получить расстояние редактирования и сопоставление путем сравнения с лимитом.

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

Для регулярных выражений вам, возможно, придется использовать экспериментальные секции code , возможно, что-то вроде этого: 

m/ (?i: [new] | \p{Alpha} (?{ $misses++ }) ){2,4}
   \s+
  (?i: [york] | \p{Alpha} (?{ $misses++ }) ){3,5}
 /x

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

2 голосов
/ 11 ноября 2010

Рассматривали ли вы двухэтапный тест, используя регулярное выражение для обеспечения выполнения требования [0-9]{2,2} (.*), затем захватывая оставшийся текст и проводя нечеткое сопоставление с ним?Попробуйте представить проблему как пересечение регулярного выражения и нечеткой строки.

1 голос
/ 19 ноября 2010

Хотя вы указали perl, в R встроен полезный алгоритм, который реализует расстояния редактирования Левенштейна. 

agrep()

Эта команда также позволяет использовать любое регулярное выражение или шаблон для сопоставления. Я бы порекомендовал вам взглянуть на это. http://stat.ethz.ch/R-manual/R-devel/library/base/html/agrep.html

...