Интересный и очень полезный алгоритм «дистанция Левенштейна» (Levenshtein distance), так же известная как редакционное расстояние или дистанция редактирования.
Эта «дистанция» — это минимальное количество правок одной строки (под правками подразумеваются три возможные операции: стирание символа, замена символа и вставка символа), чтобы превратить ее во вторую.
Вот ниже пример его реализации на abap
REPORT zlevenshtein. *----------------------------------------------------------------------* * CLASS lcl_levenshtein DEFINITION *----------------------------------------------------------------------* * *----------------------------------------------------------------------* PUBLIC SECTION. distance IMPORTING i_s TYPE csequence i_t TYPE csequence RETURNING value(r) TYPE i. *----------------------------------------------------------------------* * CLASS lcl_levenshtein IMPLEMENTATION *----------------------------------------------------------------------* * *----------------------------------------------------------------------* DEFINE m_get. l_m_index = ( ( l_l_t * ( l_m_i + ( &2 ) ) ) + l_m_j + ( &1 ) ) + 1 . read table l_d into r index l_m_index. l_v TYPE SORTED TABLE OF i WITH UNIQUE KEY table_line, l_cost TYPE i, l_m_i TYPE i, l_m_j TYPE i, l_m_index TYPE i, l_l_s TYPE i, l_l_t TYPE i. l_l_s = STRLEN( i_s ). l_l_t = STRLEN( i_t ). l_m_i = sy-index - 1. l_m_j = sy-index - 1. r = l_m_i. r = l_m_j. ELSE. l_cost = 0. ELSE. l_cost = 1. CLEAR l_v. m_get: -1 0 1, 0 -1 1, -1 -1 l_cost. READ TABLE l_v INTO r INDEX 1. d = lcl_levenshtein=>distance( i_s = 'sitting' i_t = 'kitten' ).
Так же есть статья в которой описано как реализовать этот алгоритм в других языках программирования: Algorithm Implementation/Strings/Levenshtein distance
Еще одна ссылка по этому алгоритму :Расстояние Левенштейна — определяем «похожесть» строк