Расстояние Левенштейна — определяем «похожесть» строк

Интересный и очень полезный алгоритм «дистанция Левенштейна» (Levenshtein distance), так же известная как редакционное расстояние или дистанция редактирования.

Эта «дистанция» — это минимальное количество правок одной строки (под правками подразумеваются три возможные операции: стирание символа, замена символа и вставка символа), чтобы превратить ее во вторую.

Вот ниже пример его реализации на abap

  1. REPORT  zlevenshtein.
  2. *----------------------------------------------------------------------*
  3. *       CLASS lcl_levenshtein DEFINITION
  4. *----------------------------------------------------------------------*
  5. *
  6. *----------------------------------------------------------------------*
  7. CLASS lcl_levenshtein DEFINITION.
  8.   PUBLIC SECTION.
  9.     CLASS-METHODS:
  10.       distance IMPORTING i_s TYPE csequence
  11.                          i_t TYPE csequence
  12.                RETURNING value(r) TYPE i.
  13. ENDCLASS.                    "lcl_c DEFINITION
  14. *----------------------------------------------------------------------*
  15. *       CLASS lcl_levenshtein IMPLEMENTATION
  16. *----------------------------------------------------------------------*
  17. *
  18. *----------------------------------------------------------------------*
  19. CLASS lcl_levenshtein IMPLEMENTATION.
  20.   METHOD distance.
  21.     DEFINE m_get.
  22.       l_m_index = ( ( l_l_t * ( l_m_i + ( &2 ) ) ) + l_m_j + ( &1 ) ) + 1 .
  23.       read table l_d into r index l_m_index.
  24.       add &3 to r.
  25.       insert r into table l_v.
  26.     END-OF-DEFINITION.
  27.     DATA: l_d       TYPE STANDARD TABLE OF i,
  28.           l_v       TYPE SORTED TABLE OF i WITH UNIQUE KEY table_line,
  29.           l_cost    TYPE i,
  30.           l_m_i     TYPE i,
  31.           l_m_j     TYPE i,
  32.           l_m_index TYPE i,
  33.           l_l_s     TYPE i,
  34.           l_l_t     TYPE i.
  35.  
  36.     l_l_s = STRLEN( i_s ).
  37.     l_l_t = STRLEN( i_t ).
  38.  
  39.     DO l_l_s TIMES.
  40.       l_m_i = sy-index - 1.
  41.  
  42.       DO l_l_t TIMES. "#EC CI_NESTED
  43.         l_m_j = sy-index - 1.
  44.  
  45.         IF l_m_j = 0.
  46.           r = l_m_i.
  47.         ELSEIF l_m_i = 0.
  48.           r = l_m_j.
  49.         ELSE.
  50.           IF i_s+l_m_i(1) = i_t+l_m_j(1).
  51.             l_cost = 0.
  52.           ELSE.
  53.             l_cost = 1.
  54.           ENDIF.
  55.  
  56.           CLEAR l_v.
  57.           m_get: -1  0 1, 0 -1 1, -1 -1 l_cost.
  58.           READ TABLE l_v INTO r INDEX 1.
  59.         ENDIF.
  60.         APPEND r TO l_d.
  61.  
  62.       ENDDO.
  63.     ENDDO.
  64.   ENDMETHOD.                    "distance
  65. ENDCLASS.                    "lcl_levenshtein IMPLEMENTATION
  66.  
  67. START-OF-SELECTION.
  68.   DATA: d TYPE i.
  69.  
  70.   d = lcl_levenshtein=>distance( i_s = 'sitting' i_t = 'kitten' ).
  71.   WRITE: / d.

Так же есть статья в которой описано как реализовать этот алгоритм в других языках программирования: Algorithm Implementation/Strings/Levenshtein distance

Еще одна ссылка по этому алгоритму :Расстояние Левенштейна — определяем «похожесть» строк

inikolax  Черкашин Николай  ENRC BTS

Комментарии