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

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

На нашем сайте недавно публиковался материал посвященный алгоритму определения похожести строк - расстоянию Левенштейна: 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.

Комментарии