Алгоритмы для "нечеткого соответствия" строк - PullRequest
Новая
       6

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

24 голосов
/ 23 мая 2010

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

Ответы [ 6 ]

31 голосов
/ 24 мая 2010

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

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

Задача

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

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

Анализ

Первые два требования можно суммировать примерно так: для ввода 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)]

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

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

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

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

9 голосов
/ 11 января 2011

Алгоритмы Левенштейна «Редактировать расстояние» определенно будут работать над тем, что вы пытаетесь сделать: они дадут вам оценку того, насколько близко два слова или адреса или номера телефонов, псалмы, монологи и научные статьи соответствуют друг другу, что позволяет вам Вы оцениваете результаты и выбираете лучший матч.

Более легким подходом приложения является подсчет общих подстрок: он не так хорош, как Левенштейн, но он дает полезные результаты и быстро работает на медленных языках, которые имеют доступ к быстрым функциям 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 > 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 > 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 > 1 And j > 1 Then
                sBefore1 = left(s1, i - 1)
                sBefore2 = left(s2, j - 1)
                iScore = SumOfCommonStrings(sBefore1, _
                                            sBefore2, _
                                            Compare, _
                                            iScore)
            End If


            If i + len1 < n And j + len1 < 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 < min Then
        min = b
  End If

  If c < min Then
        min = c
  End If

  Minimum = min

End Function
3 голосов
/ 16 мая 2013

На самом деле я создаю что-то похожее на плагины 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":

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

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

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

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

3 голосов
/ 23 мая 2010

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

  1. Liquidmetal
  2. Лучшее Ido Flex-Matching
2 голосов
/ 31 октября 2014

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

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

0 голосов
/ 23 мая 2010

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

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

...