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

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

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

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

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

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

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

Комментарии