Алгоритмы для строк "нечеткого соответствия"

По нечеткому согласованию я не имею в виду аналогичные строки по расстоянию Левенштейна или чему-то подобному, но так, как он использовался в TextMate/Ido/Icicles: заданный список строк, найдите те, которые включают все символы в строке поиска, но возможно, с другими символами между ними, предпочитая наилучшее соответствие.

Ответ 1

Я наконец понял, что вы искали. Проблема интересна, однако, глядя на 2 алгоритма, которые вы обнаружили, кажется, что люди имеют разные мнения о спецификациях;)

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

Проблема

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

Ожидается, что все буквы ввода будут в ключевом слове
Ожидается, что буквы на входе будут в том же порядке в ключевом слове
Список возвращаемых ключевых слов должен быть представлен в последовательном (воспроизводимом) порядке.
Алгоритм должен быть нечувствительным к регистру

Анализ:

Первые два требования можно суммировать следующим образом: для ввода axg мы ищем слова, соответствующие этому регулярному выражению [^a]*a[^x]*x[^g]*g.*

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

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

Нет никакой точности в отношении обработки символов юникода, например, à, аналогичного a или другого символа вообще? Поскольку я не знаю ни одного языка, который в настоящее время использует такие символы в своих ключевых словах, я дам ему пропустить пока.

Мое решение:

Для любого ввода я бы построил регулярное выражение, выраженное ранее. Он подходит для Python, потому что язык уже содержит нечувствительность к регистру.

Затем я сопоставлял список (по алфавиту сортировки) ключевых слов и выводил его таким образом.

В псевдокоде:

WORDS = ['Bar', 'Foo', 'FooBar', 'Other']

def GetList(input, words = WORDS):
  expr = ['[^' + i + ']*' + i for i in input]
  return [w for w in words if re.match(expr, w, re.IGNORECASE)]

Я мог бы использовать один-лайнер, но думал, что это закроет код;)

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

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

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

Ответ 2

Алгоритмы Levenshtein 'Edit Distance' определенно будут работать над тем, что вы пытаетесь сделать: они дадут вам оценку того, насколько близко друг к другу подходят два слова или адреса или номера телефонов, псалмы, монологи и научные статьи, что позволяет вам вы оцениваете результаты и выбираете наилучшее соответствие.

Более легкая аппроксимация заключается в подсчете общих подстрок: она не так хороша, как Levenshtein, но обеспечивает полезные результаты и быстро запускается на медленных языках, которые имеют доступ к быстрым функциям InString.

Я опубликовал Excel "Fuzzy Lookup" в Excellerando несколько лет назад, используя функцию FuzzyMatchScore, которая, насколько я могу судить, именно то, что вам нужно:

http://excellerando.blogspot.com/2010/03/vlookup-with-fuzzy-matching-to-get.html

Это, конечно, в Visual Basic для приложений. Будьте осторожны, распятия и чеснок:

Public Function SumOfCommonStrings( _
                            ByVal s1 As String, _
                            ByVal s2 As String, _
                            Optional Compare As VBA.VbCompareMethod = vbTextCompare, _
                            Optional iScore As Integer = 0 _
                                ) As Integer

Application.Volatile False

' N.Heffernan 06 June 2006 
' THIS CODE IS IN THE PUBLIC DOMAIN


' Function to measure how much of String 1 is made up of substrings found in String 2

' This function uses a modified Longest Common String algorithm.
' Simple LCS algorithms are unduly sensitive to single-letter
' deletions/changes near the midpoint of the test words, eg:
' Wednesday is obviously closer to WedXesday on an edit-distance
' basis than it is to WednesXXX. So it would be better to score
' the 'Wed' as well as the 'esday' and add up the total matched

' Watch out for strings of differing lengths:
'
'    SumOfCommonStrings("Wednesday", "WednesXXXday")
'
' This scores the same as:
'
'     SumOfCommonStrings("Wednesday", "Wednesday")
'
' So make sure the calling function uses the length of the longest
' string when calculating the degree of similarity from this score.


' This is coded for clarity, not for performance.

Dim arr() As Integer    ' Scoring matrix
Dim n As Integer        ' length of s1
Dim m As Integer        ' length of s2
Dim i As Integer        ' start position in s1
Dim j As Integer        ' start position in s2
Dim subs1 As String     ' a substring of s1
Dim len1 As Integer     ' length of subs1

Dim sBefore1            ' documented in the code
Dim sBefore2
Dim sAfter1
Dim sAfter2

Dim s3 As String


SumOfCommonStrings = iScore

n = Len(s1)
m = Len(s2)

If s1 = s2 Then
    SumOfCommonStrings = n
    Exit Function
End If

If n = 0 Or m = 0 Then
    Exit Function
End If

's1 should always be the shorter of the two strings:
If n &GT; m Then
    s3 = s2
    s2 = s1
    s1 = s3
    n = Len(s1)
    m = Len(s2)
End If

n = Len(s1)
m = Len(s2)

' Special case: s1 is n exact substring of s2
If InStr(1, s2, s1, Compare) Then
    SumOfCommonStrings = n
    Exit Function
End If

For len1 = n To 1 Step -1

    For i = 1 To n - len1 + 1

        subs1 = Mid(s1, i, len1)
        j = 0
        j = InStr(1, s2, subs1, Compare)

        If j &GT; 0 Then

            ' We've found a matching substring...
            iScore = iScore + len1            

          ' Now clip out this substring from s1 and s2...
          ' And search the fragments before and after this excision:


            If i &GT; 1 And j &GT; 1 Then
                sBefore1 = left(s1, i - 1)
                sBefore2 = left(s2, j - 1)
                iScore = SumOfCommonStrings(sBefore1, _
                                            sBefore2, _
                                            Compare, _
                                            iScore)
            End If


            If i + len1 &LT; n And j + len1 &LT; m Then
                sAfter1 = right(s1, n + 1 - i - len1)
                sAfter2 = right(s2, m + 1 - j - len1)
                iScore = SumOfCommonStrings(sAfter1, _
                                            sAfter2, _
                                            Compare, _
                                            iScore)
            End If


            SumOfCommonStrings = iScore
            Exit Function

        End If

    Next


Next


End Function


Private Function Minimum(ByVal a As Integer, _
                         ByVal b As Integer, _
                         ByVal c As Integer) As Integer
Dim min As Integer

  min = a

  If b &LT; min Then
        min = b
  End If

  If c &LT; min Then
        min = c
  End If

  Minimum = min

End Function

Ответ 3

Два алгоритма, которые я нашел до сих пор:

Ответ 4

На самом деле я создаю нечто похожее на Vim Command-T и ctrlp-плагины для Emacs, просто для удовольствия. Я только что провел плодотворную дискуссию с некоторыми умными сотрудниками о том, как это сделать наиболее эффективно. Цель состоит в том, чтобы уменьшить количество операций, необходимых для устранения файлов, которые не совпадают. Таким образом, мы создаем вложенную карту, где на верхнем уровне каждый ключ является символом, который появляется где-то в наборе поиска, сопоставляя индексы всех строк в наборе поиска. Затем каждый из этих индексов отображает список смещений символов, в которых этот конкретный символ появляется в строке поиска.

В псевдокоде для строк:

контроллер
модель
вид

Мы построили такую карту:

{
  "c" => {
           0 => [0]
         },
  "o" => {
           0 => [1, 5],
           1 => [1]
         },
  "n" => {
           0 => [2]
         },
  "t" => {
           0 => [3]
         },
  "r" => {
           0 => [4, 9]
         },
  "l" => {
           0 => [6, 7],
           1 => [4]
         },
  "e" => {
           0 => [9],
           1 => [3],
           2 => [2]
         },
  "m" => {
           1 => [0]
         },
  "d" => {
           1 => [2]
         },
  "v" => {
           2 => [0]
         },
  "i" => {
           2 => [1]
         },
  "w" => {
           2 => [3]
         }
}

Итак, теперь у вас есть такое отображение:

{
  character-1 => {
    word-index-1 => [occurrence-1, occurrence-2, occurrence-n, ...],
    word-index-n => [ ... ],
    ...
  },
  character-n => {
    ...
  },
  ...
}

Теперь ищем строку "oe":

Инициализируйте новую карту, где ключи будут индексами строк, которые соответствуют, и значения, которые сдвиг читает через эту строку.
Используйте первый char из строки поиска "o" и найдите его в таблице поиска.
Так как строки с индексами 0 и 1 соответствуют "o", поместите их на карту {0 => 1, 1 => 1}.
Теперь выполните поиск следующего char во входной строке, "e" и запустите его в таблице.
Здесь три строки соответствуют, но мы знаем, что нам нужны только строки 0 и 1.
Проверьте, есть ли какие-либо смещения > текущие смещения. Если нет, удалите элементы с нашей карты, иначе обновите смещение: {0 => 9, 1 => 3}.

Теперь, взглянув на ключи на нашей карте, которые мы накопили, мы знаем, какие строки соответствуют нечеткому поиску.

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

Интересная вещь в том, что вы могли бы также эффективно хранить Levenstein Distance вместе с каждым матчем, предполагая, что вы будете заботиться только о вставках, а не заменах или удалениях. Хотя, возможно, и не сложно получить эту логику.

Ответ 5

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

Я подробно описал алгоритм здесь: http://blog.kazade.co.uk/2014/10/a-fuzzy-filename-matching-algorithm.html

Ответ 6

Если ваш текст преимущественно английский, вы можете попробовать свои силы при различных алгоритмах Soundex 1. Классический soundex 2. Metafone

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