Методы оценки близости строк Татьяна Кривошеева

Строковые метрики Расстояние Хэмминга Расстояние Левенштейна Расстояние Дамерай-Левенштейна, Метрика Нидлмана-Вунша, Метрика Смита-Вотермана Bag distance Метрики Jaro, Jaro-Winkler q-grams, skip-grams Общий префикс Наибольшая общая подстрока Метрика Monge-Elkan

Операции преобразования строк Подстановка kill bill Вставка kill skill Удаление fear ear

1. Расстояние Хэмминга (подстановка) d H (GCAT,CGAT) = 2 2. Расстояние Левенштейна (удаление, вставка, подстановка) d E (CGACG, GTCGA) = 3

Подсчет расстояния Левенштейна TEST S E T i j

TEST 0 S E T Подсчет расстояния Левенштейна 0 0

TEST 0 S1 E T Подсчет расстояния Левенштейна

TEST 0 S1 E2 T

Подсчет расстояния Левенштейна TEST 0 S1 E2 T3

Подсчет расстояния Левенштейна TEST S1 E2 T3

Подсчет расстояния Левенштейна TEST S11 E2 T3

Подсчет расстояния Левенштейна TEST S11223 E22123 T32222

Расстояние Дамерау-Левенштейна (перестановка соседних символов) d DL (GCAT,CGAT) = 1 Метрика Нидлмана-Вунша (за операции вставки, удаления, подстановки можно получить разный штраф) delete (c) = 1 insert (c) = 2 substitute (c) = 3 Метрика Смита-Вотермана (штраф за операцию зависит от символа) delete (A) = 2 delete (B) = 0.1

Штраф за пропуски Константный штраф d C (gov, government) = 3 Линейный штраф d L (gov, government) = 3 * 7 = 21 Афинный штраф d A (gov, government) = * 2 = 15

bag dist (s,t) = max( IM(s) \ M(t)|, |M(t) \ M(s)|) М(Х) – мультимножество символов строки Х Bag distance (Bartolini, 2002)

Bag distance metric s = bread t = beer M(s) = {b,r,e,a,d} M(t) = {b,e,e,r} M(s) \ M(t) = { a, d } M(t) \ M(s) = { e } bag dist (s,t) = max (I{ a, d }I, I{ e }I) = 2

Jaro metric (Winkler, 1999) J(s,t) = *(IsI/IsI + ItI/ItI + (IsI – [T s,t /2])/IsI) s = a 1 a 2...a k t = b 1...b L s и t строки общих символов s и t T s,t количество транспозиций

Jaro metric (Winkler, 1999) Общие символы a i = b j R = [max(IsI,ItI)/2] - 1 a i b i-R b i b i+R s t

Jaro metric 1. s = CRETA t = TRACES 2. R = [max(|s|, |t|)/2] – 1 = [max(5, 6)/ 2] -1 =2 3. s = REA t = RAE 4. T st = 2 J(s,t) = *(IsI/IsI + ItI/ItI + (IsI – [T s,t /2])/IsI) = *(3/5 + 3/6 + (3 – [2/2])/3) = 0.59

Jaro-Winkler metric JW(s,t) = J(s,t) + α* boost(s,t)*(1-J(s,t)) boost(s,t) = min( ILcp(s,t)I, p) s = DIXON t = DICKSONX J(s,t) = α = 0.1 p = 2 Lcp(s,t) = DI boost(s,t) = min (2, 2) = 2 JW(s,t) = *2 *(1 – 0.767) = 0.813

q-grams metric (Gravano, 2001) q-gram – подстрока заданной строки длины q s = MARTHA q = 2 G 2 (s) = { #M,MA, AR, RT, TH, HA, A#} q = 3 G 3 (s) = { ##M,#MA,MAR, ART, RTH, THA,HA#,A##}

q-grams metric s = MARTHA t = MARCH G 2 (s) = { #M,MA, AR, RT, TH, HA, А#} G 2 (t) = { #M,MA, AR, RC, CH, H#} q-gram(s,t) = 3 / max(7, 6) = 0.43

Skip-gram metric (Keskustalo, 2003) Skip-gram – q-грамма, которая может состоять из несоседних символов s = MARTHA q = 2 skip{0,1} G skip{0,1} (s)={#M,#A,MA,MR,AR,AT, RH,TA,RT,TH, HA,A#, H#}

Общий префикс(Common Prefix) 2 CP α (s,t) = (|Lcp(s,t)| + α) / (|s| * |t|) s = MARTHA t = MARCH Lcp(s,t) = 3 α = 1 2 CP 1 (s,t) = (3 + 1) / (6 * 5) = 0.53

Наибольшая общая подстрока 0, |Lcs(s,t)| < k |Lcs(s,t)| + LCS(s -Lcs(s,t), t -Lcs(s,t) ) s = abcdeftg t = bcdaefg k = 2 s = abcdeftg t = bcdaefg LCS(s,t) = 3 + LCS(aeftg, aefg) s -Lcs(s,t) = aeftg t -Lcs(s,t) = aefg LCS(s,t)= LCS(tg, g) = 6 { LCS(s,t) =

Weighted LCS |Lcs(s,t)| + α – max( α,p) |Lcs(s,t)| + α w Lcs(s,t) =

Monge-Elkan (Monge and Elkan, 1996) s = {s 1 s 2..s K } t = {t 1 t 2..t L } Monge-Elkan(s,t) = 1/K * Ʃ max sim(s i,t j ) sim(s i,t j ) – любая метрика для сравнения двух строк K i=1j=1..L

Наборы тестирующих данных 1.Польские имена (1457) 2.Полные польские имена (1219)

Результаты исследования Польские имена WLCS CP α Полные польские имена WLCS Smith-Waterman metric JWM 0.976

Конец доклада Вопросы?