Методы оценки близости строк Строковые метрики




НазваниеМетоды оценки близости строк Строковые метрики
Дата конвертации12.05.2013
Размер445 b.
ТипПрезентации


Методы оценки близости строк


Строковые метрики

  • Расстояние Хэмминга

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

  • Расстояние Дамерай-Левенштейна,

  • Метрика Нидлмана-Вунша,

  • Метрика Смита-Вотермана

  • Bag distance

  • Метрики Jaro, Jaro-Winkler

  • q-grams, skip-grams

  • Общий префикс

  • Наибольшая общая подстрока

  • Метрика Monge-Elkan



Операции преобразования строк

  • Подстановка kill bill

  • Вставка kill skill

  • Удаление fear ear





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





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



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



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



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



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



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



Расстояние Дамерау-Левенштейна

  • Расстояние Дамерау-Левенштейна

  • (перестановка соседних символов)

  • dDL(GCAT,CGAT) = 1

  • Метрика Нидлмана-Вунша

  • (за операции вставки, удаления, подстановки можно получить разный штраф)

  • delete (c) = 1 insert (c) = 2 substitute (c) = 3

  • Метрика Смита-Вотермана

  • (штраф за операцию зависит от символа)

  • delete (‘A’) = 2 delete (‘B’) = 0.1



Штраф за пропуски

  • Константный штраф

  • dC(“gov”, “government”) = 3

  • Линейный штраф

  • dL(“gov”, “government”) = 3 * 7 = 21

  • Афинный штраф

  • dA(“gov”, “government”) = 3 + 6 * 2 = 15



Bag distance (Bartolini, 2002)

  • bagdist(s,t) = max( IM(s) \ M(t)|, |M(t) \ M(s)|)

  • М(Х) – мультимножество символов

  • строки Х



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’ }

  • bagdist(s,t) = max (I{ ‘a’, ‘d’ }I, I{ ‘e’ }I) = 2



Jaro metric (Winkler, 1999)



Jaro metric (Winkler, 1999)

  • Общие символы

  • ai = bj

  • R = [max(IsI,ItI)/2] - 1



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. Ts’t’ = 2

  • J(s,t) = ⅓*(Is’I/IsI + It’I/ItI + (Is’I – [Ts’,t’ /2])/Is’I)

  • = ⅓*(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.767 α = 0.1 p = 2

  • Lcp(s,t) = “DI”

  • boost(s,t) = min (2, 2) = 2

  • JW(s,t) = 0.767 + 0.1*2 *(1 – 0.767) = 0.813



q-grams metric (Gravano, 2001)

  • q-gram – подстрока заданной строки длины q

  • s = “MARTHA”

  • q = 2

  • G2(s) = { “#M”,“MA”, “AR”, “RT”, “TH”, “HA”, “A#”}

  • q = 3

  • G3(s) = { “##M”,“#MA”,“MAR”, “ART”, “RTH”,

  • “THA”,“HA#”,“A##”}



q-grams metric

  • s = “MARTHA” t = “MARCH”

  • G2(s) = { “#M”,“MA”, “AR”, “RT”, “TH”, “HA”, “А#”}

  • G2(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}

  • Gskip{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

  • CP1(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)= 3 + 3 + LCS(“tg”, “g”) = 6



Weighted LCS

  • |Lcs(s,t)| + α – max(α,p)



Monge-Elkan (Monge and Elkan, 1996)

  • s = {s1s2..sK} t = {t1t2..tL}

  • Monge-Elkan(s,t) = 1/K * Ʃ max sim(si,tj)

  • sim(si,tj) – любая метрика для сравнения

  • двух строк



Наборы тестирующих данных

  • Польские имена (1457)

  • Полные польские имена (1219)



Результаты исследования

  • Польские имена

  • WLCS 0.983

  • CPα 0.947

  • Полные польские имена

  • WLCS 0.992

  • Smith-Waterman metric 0.976

  • JWM 0.976



Конец доклада

  • Вопросы?



Похожие:

Методы оценки близости строк Строковые метрики iconБыстрые методы оценки Быстрые, дешевые, грязные методы оценки ранних концепций интерфейсов сайта Говорить только правду!

Методы оценки близости строк Строковые метрики iconМетоды определения семантической близости документов Области применения
Локальные: близость определяется для пары вершин и не затрагивает большинство вершин
Методы оценки близости строк Строковые метрики iconНовые методы оценки эффективности pr. Веб-аналитика для связей с общественностью. Полезное агентство для Вашего бизнеса Специфика Public Relations
Новые методы оценки эффективности pr. Веб-аналитика для связей с общественностью
Методы оценки близости строк Строковые метрики iconОсновная идея Эйнштейна была проста: материальным носителем тяготения является само пространство (точнее, пространство-время)
«искривление времени», то есть изменение временно́й компоненты метрики, g00(пространство в этом приближении евклидово). Распространение...
Методы оценки близости строк Строковые метрики iconХмурчик Андрей гуо гимназия №1 им К. Калиновского Символьные и строковые величины. Операции над символьными и строковыми величинами
Символьные и строковые величины. Операции над символьными и строковыми величинами
Методы оценки близости строк Строковые метрики iconМетоды оценки инвестиционных проектов предприятий электроэнергетики Панюкова К., Талаласова Е., Шевелева К., 447 гр. Актуальность
Цель: изучение методов оценки инвестиционных проектов предприятий электроэнергетики и обоснование наиболее подходящих методов, в...
Методы оценки близости строк Строковые метрики iconТема Методы оценки денежных потоков Лектор: к э. н., доцент Платонова Н. А

Методы оценки близости строк Строковые метрики icon24. 11. 2004: Методы структурирования оценки: swot-анализ, концептуальная карта, цветовое голосование, (В. Маршаков, Е. Кузнецова, Ю. Буссель / Политология гу-вшэ) 29. 12. 2004
Методика оценки обоснованности включения/исключения отдельных видов надзора из сферы действия закона №134-фз (А. Беляев / Гиму гу-вшэ)...
Методы оценки близости строк Строковые метрики iconСимвольные и строковые величины в Pascal abc содержание Типы данных

Методы оценки близости строк Строковые метрики iconВадим Маршаков Екатерина Кузнецова
Методы структурированной оценки: swot анализ, концептуальная карта, цветовое голосование
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница