none
Как выполнить "широкий" поиск в текстовом файле? RRS feed

  • Вопрос

  • Поясню.

     

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

     

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

     

    Честно говоря, даже самому кажется, что "миссия невыполнима"... ((( Но может быть у кого-то будут какие-нибудь идеи?

    18 июня 2007 г. 15:18

Ответы

  • Миссия выполнима! Все это давно сделано и, увы, не нами.

    Итак, вам нужна функция, являющаяся результатом сравнения двух строк, причем значение функции зависит от того, насколько строки похожи друг на друга.

    Один алгоритм состоит в вычислении т.н. длины Левенштейна. Иными словами, он подсчитывает, сколько вставок, замен и удалений символов предстоит сделать, чтобы превратить одну строку в другую. При полном совпадении строк значение функции будет наименьшим (0). Кстати, статья (см. ссылку выше) содержит листинг на Visual Basic, так что вы сможете сразу воспользоваться данным алгоритмом.

    Другой алгоритм называется Trigram method. Если упрощенно, то он состоит в разделении сравниваемых строк на всевозможные последовательности из трех идущих подряд символов. Далее подсчитывается число совпадающих трехсимвольных последовательностей. Для одинаковых строк функция принимает наибольшее значение. К сожалению, статья содержит листинг программы только на Perl, и вам придется переписывать ее под vbScript.

    Для  того чтобы работать со строками разной длины, видимо, следует делить полученный коэффициент на количество символов (трехсимвольных последовательностей) в более длинной строке. И, надеюсь, понятно, что выбор порогового значения функии, при пересечении которого строки уже не считаются "почти совпадающими", является достаточно субъективным.

    18 июня 2007 г. 20:32
    Модератор
  • Вот функция, адаптированная под vbScript. Она работает.


    Code Snippet

    '*******************************
    '*** Get minimum of three values
    '*******************************

    Private Function Minimum(a, b, c)

    Dim mi
                             
      mi = a
      If b < mi Then
        mi = b
      End If
      If c < mi Then
        mi = c
      End If
     
      Minimum = mi
                             
    End Function

    '********************************
    '*** Compute Levenshtein Distance
    '********************************

    Public Function LD(s, t)

    Dim d()  ' matrix
    Dim m    ' length of t
    Dim n    ' length of s
    Dim i    ' iterates through s
    Dim j    ' iterates through t
    Dim s_i  ' ith character of s
    Dim t_j  ' jth character of t
    Dim cost ' cost
     
      ' Step 1
      n = Len(s)
      m = Len(t)
      If n = 0 Then
        LD = m
        Exit Function
      End If
      If m = 0 Then
        LD = n
        Exit Function
      End If
      ReDim d(n, m)
     
      ' Step 2
      For i = 0 To n
        d(i, 0) = i
      Next
      For j = 0 To m
        d(0, j) = j
      Next

      ' Step 3
      For i = 1 To n
        s_i = Mid(s, i, 1)

        ' Step 4
        For j = 1 To m
          t_j = Mid(t, j, 1)
         
          ' Step 5
          If s_i = t_j Then
            cost = 0
          Else
            cost = 1
          End If
         
          ' Step 6
          d(i, j) = Minimum(d(i - 1, j) + 1, d(i, j - 1) + 1, d(i - 1, j - 1) + cost)
        Next
      Next
     
      ' Step 7
      LD = d(n, m)
     
    End Function

     

     

    26 июня 2007 г. 20:54
    Модератор

Все ответы

  • Миссия выполнима! Все это давно сделано и, увы, не нами.

    Итак, вам нужна функция, являющаяся результатом сравнения двух строк, причем значение функции зависит от того, насколько строки похожи друг на друга.

    Один алгоритм состоит в вычислении т.н. длины Левенштейна. Иными словами, он подсчитывает, сколько вставок, замен и удалений символов предстоит сделать, чтобы превратить одну строку в другую. При полном совпадении строк значение функции будет наименьшим (0). Кстати, статья (см. ссылку выше) содержит листинг на Visual Basic, так что вы сможете сразу воспользоваться данным алгоритмом.

    Другой алгоритм называется Trigram method. Если упрощенно, то он состоит в разделении сравниваемых строк на всевозможные последовательности из трех идущих подряд символов. Далее подсчитывается число совпадающих трехсимвольных последовательностей. Для одинаковых строк функция принимает наибольшее значение. К сожалению, статья содержит листинг программы только на Perl, и вам придется переписывать ее под vbScript.

    Для  того чтобы работать со строками разной длины, видимо, следует делить полученный коэффициент на количество символов (трехсимвольных последовательностей) в более длинной строке. И, надеюсь, понятно, что выбор порогового значения функии, при пересечении которого строки уже не считаются "почти совпадающими", является достаточно субъективным.

    18 июня 2007 г. 20:32
    Модератор
  • Спасибо Вам огромное!!! Всегда удивительно, что ТО, что казалось таким сложным, на самом деле имеет логичное и простое решение!!!  И вдвойне приятно, что находятс люди, которым не лень подсказать правильное решение таким самоМучкам, как я! )))))
    19 июня 2007 г. 6:23
  • Добавлю, что Perl под Windows тоже есть под названием Active Perl
    19 июня 2007 г. 8:31
    Модератор
  •  osr. написано:

    Миссия выполнима! Все это давно сделано и, увы, не нами.

    Итак, вам нужна функция, являющаяся результатом сравнения двух строк, причем значение функции зависит от того, насколько строки похожи друг на друга.

    Один алгоритм состоит в вычислении т.н. длины Левенштейна. Иными словами, он подсчитывает, сколько вставок, замен и удалений символов предстоит сделать, чтобы превратить одну строку в другую. При полном совпадении строк значение функции будет наименьшим (0). Кстати, статья (см. ссылку выше) содержит листинг на Visual Basic, так что вы сможете сразу воспользоваться данным алгоритмом.

    Другой алгоритм называется Trigram method. Если упрощенно, то он состоит в разделении сравниваемых строк на всевозможные последовательности из трех идущих подряд символов. Далее подсчитывается число совпадающих трехсимвольных последовательностей. Для одинаковых строк функция принимает наибольшее значение. К сожалению, статья содержит листинг программы только на Perl, и вам придется переписывать ее под vbScript.

    Для  того чтобы работать со строками разной длины, видимо, следует делить полученный коэффициент на количество символов (трехсимвольных последовательностей) в более длинной строке. И, надеюсь, понятно, что выбор порогового значения функии, при пересечении которого строки уже не считаются "почти совпадающими", является достаточно субъективным.

     

    И снова я со своей проблемой...

    Пытался "поднять" этот листинг по Левенштейну, но, к сожалению, видно не хватает ума...

    На самом начале выдает ошибку "Ошибка компиляции Microsoft BLOCKED SCRIPT Предполагается наличие ")" "... И дальше этого дело не идет... Все мои попытки реанимировать данный процесс провалились...

     

    Может быть подскажете, в чем может быть проблема? Может быть у меня старая версия VdsEdit?

    26 июня 2007 г. 8:12
  • Дело в том, что приведенная программа написана на Visual Basic, а нам требуется vbScript. Отличия есть, например, в vbScript не определяется тип переменных (они там все Variant). Если готовы ожидать, я попробую переделать программу, но когда будет время.
    26 июня 2007 г. 9:07
    Модератор
  •  osr. написано:
    Дело в том, что приведенная программа написана на Visual Basic, а нам требуется vbScript. Отличия есть, например, в vbScript не определяется тип переменных (они там все Variant). Если готовы ожидать, я попробую переделать программу, но когда будет время.

     

    Конечно, поожидаю!  Естественно, если Вас это не затруднит! Заранее благодарю!!!

    26 июня 2007 г. 10:11
  • Вот функция, адаптированная под vbScript. Она работает.


    Code Snippet

    '*******************************
    '*** Get minimum of three values
    '*******************************

    Private Function Minimum(a, b, c)

    Dim mi
                             
      mi = a
      If b < mi Then
        mi = b
      End If
      If c < mi Then
        mi = c
      End If
     
      Minimum = mi
                             
    End Function

    '********************************
    '*** Compute Levenshtein Distance
    '********************************

    Public Function LD(s, t)

    Dim d()  ' matrix
    Dim m    ' length of t
    Dim n    ' length of s
    Dim i    ' iterates through s
    Dim j    ' iterates through t
    Dim s_i  ' ith character of s
    Dim t_j  ' jth character of t
    Dim cost ' cost
     
      ' Step 1
      n = Len(s)
      m = Len(t)
      If n = 0 Then
        LD = m
        Exit Function
      End If
      If m = 0 Then
        LD = n
        Exit Function
      End If
      ReDim d(n, m)
     
      ' Step 2
      For i = 0 To n
        d(i, 0) = i
      Next
      For j = 0 To m
        d(0, j) = j
      Next

      ' Step 3
      For i = 1 To n
        s_i = Mid(s, i, 1)

        ' Step 4
        For j = 1 To m
          t_j = Mid(t, j, 1)
         
          ' Step 5
          If s_i = t_j Then
            cost = 0
          Else
            cost = 1
          End If
         
          ' Step 6
          d(i, j) = Minimum(d(i - 1, j) + 1, d(i, j - 1) + 1, d(i - 1, j - 1) + cost)
        Next
      Next
     
      ' Step 7
      LD = d(n, m)
     
    End Function

     

     

    26 июня 2007 г. 20:54
    Модератор