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

Ответ 1

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

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

Попробуйте следующее:

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

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

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

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

Ответ 2

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

Что-то вроде этого (предполагая, что ваш ввод - это строки из файла)

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
    }
}

Ответ 3

Разделите проблему на две части:

• Совместите двузначное число.
• Беспокойство соответствует остатку против "Нью-Йорка".

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

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

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

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

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

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

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

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

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

Ответ 7

Правило большого пальца: когда вам нужно перейти в Qaru и спросить: "Как я могу сделать 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+)" дополнительным, чтобы упростить регулярное выражение, чтобы вы могли понять его суть. Для этого вам, вероятно, придется прибегнуть к именованным захватам и группе (?:) non-captureuring. Я не хотел вникать во все это, просто хотел помочь вам понять, как я подхожу к этому.

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

Ответ 8

Вы изучали использование модуля Jarkkos String:: Approx в CPAN? Он имеет в нем алгоритм agrep, но намного медленнее, чем Udis.

Ответ 9

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

agrep()

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