сравнение строк

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

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

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

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

  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.
Подписка на сравнение строк