Расстояние Левенштейна

Быстрая функция расстояния Левенштейна

Здравствуйте.

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

Далее прикладываю код оптимизированной процедуры. Пользуйтесь на здоровье.

  1. form dist using s1 type csequence s2 type csequence CHANGING res TYPE i.
  2. ntab TYPE table OF i,
  3. otab TYPE table of i,
  4. ls1 type i, ls2 type i,
  5. t1 type i, t2 type i,
  6. tt2 type i,
  7. x1 type i, x2 type i,
  8. x type i,
  9. inp type i.
  10.  
  11. ls1 = strlen( s1 ) - 1.
  12. ls2 = strlen( s2 ) - 1.
  13. do.
  14. do.
  15. if s1+t1(1) = s2+t2(1).
  16. if t1 = 0.
  17. inp = t2.
  18. elseif t2 = 0.
  19. inp = t1.
  20. read table otab into inp index t2.
  21. insert inp into table ntab.
  22. if t1 = 0.
  23. inp = t2 + 1.
  24. elseif t2 = 0.
  25. inp = t1 + 1.
  26. tt2 = t2 + 1.
  27. read table ntab into x index t2.
  28. read table otab into x1 index t2.
  29. read table otab into x2 index tt2.
  30. if x < x1.
  31. if x < X2.
  32. inp = x + 1.
  33. inp = x2 + 1.
  34. if x1 < x2.
  35. inp = x1 + 1.
  36. inp = x2 + 1.
  37. insert inp into table ntab.
  38. if t2 = ls2.
  39. t2 = 0.
  40. t2 = t2 + 1.
  41. refresh otab.
  42. otab[] = ntab[].
  43. refresh ntab.
  44. if t1 = ls1.
  45. t1 = t1 + 1.
  46. res = inp.

Правильная функция расстояния Левенштейна

Здравствуйте.

На нашем сайте недавно публиковался материал посвященный алгоритму определения похожести строк - расстоянию Левенштейна: http://abap.kz/blog/74/user/inikolax . Автор материала inikolax

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

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

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

Далее прикладываю исходный код процедуры, вы можете его оптимизировать ещё больше, и опубликовать на нашем сайте.

Спасибо за внимание.

  1. form dist using s1 type csequence s2 type csequence CHANGING res TYPE i.
  2. BEGIN OF rec,
  3. i1 type i,
  4. i2 type i,
  5. d type i,
  6. end of rec.
  7. ztab type HASHED TABLE OF rec WITH UNIQUE key i1 i2,
  8. rtab type rec,
  9. mtab type rec,
  10. mtab1 type rec,
  11. mtab2 type rec,
  12. ls1 type i, ls2 type i, t1 type i, t2 type i, tt1 type i, tt2 type i.
  13.  
  14. ls1 = strlen( s1 ).
  15. ls2 = strlen( s2 ).
  16. t1 = 1.
  17. t2 = 1.
  18. do.
  19. do.
  20. tt1 = t1 - 1.
  21. tt2 = t2 - 1.
  22. rtab-i1 = t1.
  23. rtab-i2 = t2.
  24. if s1+tt1(1) = s2+tt2(1).
  25. if tt1 = 0.
  26. rtab-d = tt2.
  27. elseif tt2 = 0.
  28. rtab-d = tt1.
  29. read table ztab WITH TABLE KEY i1 = tt1 i2 = tt2 into mtab.
  30. rtab-d = mtab-d.
  31. insert rtab into table ztab.
  32. if tt1 = 0.
  33. rtab-d = t2.
  34. elseif tt2 = 0.
  35. rtab-d = t1.
  36. read table ztab WITH TABLE KEY i1 = tt1 i2 = tt2 into mtab.
  37. read table ztab WITH TABLE KEY i1 = tt1 i2 = t2 into mtab1.
  38. read table ztab WITH TABLE KEY i1 = t1 i2 = tt2 into mtab2.
  39. if mtab-d < mtab1-d.
  40. if mtab-d < mtab2-d.
  41. rtab-d = mtab-d + 1.
  42. rtab-d = mtab2-d + 1.
  43. if mtab1-d < mtab2-d.
  44. rtab-d = mtab1-d + 1.
  45. rtab-d = mtab2-d + 1.
  46. insert rtab into table ztab.
  47. if t2 = ls2.
  48. t2 = 1.
  49. t2 = t2 + 1.
  50. if t1 = ls1.
  51. t1 = t1 + 1.
  52. res = rtab-d.

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

Интересный и очень полезный алгоритм «дистанция Левенштейна» (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

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

Подписка на Расстояние Левенштейна