Лингвистика для математиков. Исправление опечаток 2 + Токенизация

1. Лингвистика для математиков

Исправление опечаток 2 + Токенизация

2. Soundex

Soundex — это алгоритм для кодирования имён собственных.
1918–1922 гг. в США Роберт Расселл и Маргарет Кинг Оделл
Цель: облегчить поиск похоже звучащих фамилий
В середине XX века использовался при анализе результатов переписей
населения 1890–1920 гг

3. Soundex

4.

Дан список фамилий и соответствующих им кодов Soundex в перепутанном
порядке. Некоторые символы пропущены:
Allaway, Anderson, Ashcombe, Buckingham, Chapman,
Colquhoun, Evans, Fairwright, Kingscott, Lewis,
Littlejohns, Stanmore, Stubbs, Tocher, Tonks,
Whytehead
S312, T␣6␣, ␣5␣3, C42␣, T520, L␣42, A536, C155,
␣623, S356, ␣252, ␣152, ␣330, A251, A400, L2␣0

5. Soundex

Задание 1. Опишите пошагово, как генерируется код Soundex.
Задание 2. Установите соответствия между фамилиями и кодами
Soundex и вставьте пропущенные символы.
Задание 3. Постройте коды Soundex для следующих фамилий:
Ferguson, Fitzgerald, Hamnett, Keefe, Maxwell, Razey, Shaw, Upfield.

6. Ответы

Ответ на задание 2
Allaway: A400, Anderson: A536, Ashcombe: A251, Buckingham: B252, Chapman:
C155, Colquhoun: C425, Evans: E152, Fairwright: F623, Kingscott: K523, Lewis:
L200, Littlejohns: L342, Stanmore: S356, Stubbs: S312, Tocher: T260, Tonks:
T520, Whytehead: W330.
Ответ на задание 3.
Ferguson: F622, Fitzgerald: F326, Hamnett: H530, Keefe: K100, Maxwell: M240,
Razey: R200, Shaw: S000, Upfield: U143.

7. Soundex

Проблемные моменты:
● Выкидывание h/w вообще-то портит много кейсов. (Придумайте сами
такое имя собственное)
● Для каких языков не_будет работать?
● Не учитывает вариативность произношения

8. Улучшенный Soundex

9. Улучшенный Soundex

● В среднем, на одно
значение кода Soundex
приходится 21 фамилия. В
случае же улучшенной
версии Soundex, к одному и
тому же коду преобразуются
всего 2-3 фамилии.

10. Soundex

Идея называется - нечёткий
поиск (approximate string
matching, fuzzy string
searching)
Супер реализации в python и
MySQL

11. Алгоритм Metaphone

● Придумали в 1990
● Существует для английского, бразильского португальского, испанского и
русского
● Неудобно, потому что нужно прописывать много фонетических правил,
но точнее
● Лучше, чем Soundex, потому что учитывает варианты произношения
● Не делит буквы на группы → теряет меньше информации
● кодирует слова путем уменьшения их до 16 согласных звуков: B, X, S, K,
J, T, F, H, L, M, N, P, R, 0, W, Y. Ноль представляет звук "th"; X
представляет "sh"

12. Алгоритм Metaphone

Drop duplicate adjacent letters, except for C.
If the word begins with 'KN', 'GN', 'PN', 'AE', 'WR', drop the first letter.
Drop 'B' if after 'M' at the end of the word.
'C' transforms to 'X' if followed by 'IA' or 'H' (unless in latter case, it is part of 'SCH-', in which case it transforms to 'K'). 'C' transforms to 'S' if followed by 'I',
'E', or 'Y'. Otherwise, 'C' transforms to 'K'.
● 'D' transforms to 'J' if followed by 'GE', 'GY', or 'GI'. Otherwise, 'D' transforms
to 'T'.
● Drop 'G' if followed by 'H' and 'H' is not at the end or before a vowel. Drop 'G'
if followed by 'N' or 'NED' and is at the end.

13. Алгоритм Metaphone

● 'G' transforms to 'J' if before 'I', 'E', or 'Y', and it is not in 'GG'. Otherwise, 'G'
transforms to 'K'.
● Drop 'H' if after vowel and not before a vowel.
● 'CK' transforms to 'K'.
● 'PH' transforms to 'F'.
● 'Q' transforms to 'K'.
● 'S' transforms to 'X' if followed by 'H', 'IO', or 'IA'.
● 'T' transforms to 'X' if followed by 'IA' or 'IO'. 'TH' transforms to '0'. Drop 'T' if
followed by 'CH'.

14. Алгоритм Metaphone

'V' transforms to 'F'.
'WH' transforms to 'W' if at the beginning. Drop 'W' if not followed by a vowel.
'X' transforms to 'S' if at the beginning. Otherwise, 'X' transforms to 'KS'.
Drop 'Y' if not followed by a vowel.
'Z' transforms to 'S'.
Drop all vowels unless it is the beginning.

15. Алгоритм Metaphone

ALEXANDRE → ALEKSANTRE → ALKSNTR
ALEKSANDER → ALEKSANTER → ALKSNTR

16. Алгоритм Metaphone

AKXN → Агашин, Акаченок, Акишин, Аксионенко, Аксионов, Акчунаев,
Акшанов, Акшенцев, Акшинский, Акшинцев, Акшонов.
FSLX → Василишин, Васильчак, Васильченко, Васильчик, Васильчиков,
Васильченко, Васильчук, Василющенко.
SRFM → Серафимов, Серафимский, Серафимчук, Церейфман.
Одно и то же значение кода Metaphone имеют в среднем 6 фамилий.

17. Русский Metaphone

● 2002
● Этот алгоритм преобразует к одному и тому же коду в среднем 1-2
фамилии.
● Учитывает безударные гласные и слияние согласных при произношение
● Мало правил - круто
● При это, возможно, слишком строго

18.

1. Для всех гласных букв проделать следующие операции.
ЙО, ИО, ЙЕ, ИЕ → И
О, Ы, Я → А
Е, Ё, Э → И
Ю→У
2. Для всех согласных букв, за которыми следует любая согласная, кроме
Л, М, Н или Р, либо же для согласных на конце слова, провести
оглушение:
Б→П
З→С
Д→Т
В→Ф
Г→К

19.

1. Для всех гласных букв проделать следующие операции.
ЙО, ИО, ЙЕ, ИЕ → И
О, Ы, Я → А
Е, Ё, Э → И
Ю→У
2. Для всех согласных букв, за которыми следует любая согласная, кроме
Л, М, Н или Р, либо же для согласных на конце слова, провести
оглушение:
Б→П
З→С
Д→Т
В→Ф
Г→К
3. Склеиваем ТС и ДС в Ц: ТС → Ц

20. Русский Metaphone примеры

ВИТАФСКИЙ → Витавский, Витовский.
ВИТИНБИРК → Витенберг, Виттенберг.
НАСАНАФ → Насанов, Насонов, Нассонов, Носонов.
ПИРМАКАФ → Пермаков, Пермяков, Перьмяков

21. Алгоритм Match rating approach

● Использует и фонетические правила (comparison rules and encoding
rules), и расстояния
● Полученное расстояние между словами сравнивается с минимальным
порогом
● Откуда порог?

22. Алгоритм Match rating approach

Encoding праила:
● Удалить все гласные, если они не в начале слова
● Удалить вторую согласную из всех комбинаций с двумя согласными
● Уменьшить длину кода до шести. Как? Соединить три первых и три
последний буквы
Потом similarity comparison с таблицами по необходимости

23. Алгоритм Match rating approach

24. There is more

Другие методы из серии approximate string matching:
Caverphone
NYSIIS
Daitch-Mokotoff Soundex
Double metaphone
и т.д.
https://habr.com/ru/post/114947/

25. Другие методы: применение машинного обучения

● В основном для случаев real word errors:
○
see you in five minuets! -- такие ошибки могут составлять вплоть до 15% от всех опечаток
● Как? Контекст!
● Проблема: проверять для каждого слова контекст -- долго!
Textbook example:
● Noisy channel model

26. Модель noisy channel

written text → into a spoken text

27. Модель noisy channel

28. Кто такой Питер Норвиг?

● Закодил один из простейших алгоритмов spellcheck (И всего лишь в 21
строчку кода!)
● https://norvig.com/spell-correct.html
2007 год

29. Регулярные выражения и нормализация текста

30. ELIZA - первая Алиса

31. Регулярные выражения

Что это такое?
Какой-то формальный язык,
помогающий искать в тексте/строке
какие-то паттерны
Regex: one pattern to rule them all, one
to find them. One to bring them all, and
in the darkness bind them.

32. Формальный язык

Итак: контекстные замены -- приведите пример?

33. Формальный язык

Что есть в формальном языке?
● Алфавит (конечный)
○ IPA - это алфавит
○ буквы кириллического алфавита
○ буквы латинского алфавита
○ набор грамматических категорий - тоже алфавит!
○ ?
● Слова
● Языки

34. Формальные языки

● У них есть много подвидов и даже иерархия, но об этом чуть дальше
● Регулярный язык - это самый простой формальный язык
Регулярный язык:
1. Есть фиксированный алфавит
2. Мы говорим, что в языке, основанном на этом алфавите, все слова
образуются с помощью какого-то одного (регулярного) правила

35. Правила регулярного языка

Приоритет операций: итерация, конкатенация, объединение

36. Примеры регулярных языков

37. Примеры регулярных выражений в лингвистике

38. Примеры регулярных выражений в лингвистике

39. Примеры регулярных выражений в лингвистике

40. Примеры регулярных выражений в лингвистике

41. Примеры регулярных выражений в лингвистике

42. Регулярные выражения: Хомский

Так, а причем здесь Хомский?
● Иерархия Хомского
-- классификация формальных языков и
формальных грамматик;
4 типа по их условной сложности

43. Формальная грамматика

Terminals: {s, sh, ss}
Nonterminals: {snake, I, am}
Production rules: {I → sh, am → s, snake → ss}

44. Формальная грамматика

Аналогия в синтаксисе:

45. Регулярные выражения и конечные автоматы

Есть регулярное выражение: colou?r, которое описывает такой набор слов:
{colour, color}
Как компьютер формализует, что это множество слов описывается одним
регулярным выражением/языком?

46. Регулярные выражения и конечные автоматы

colou?r -- {colour, color}

47. Нарисуйте конечные автоматы для слогов

1) для закрытого слога
2) для слова с 2 гласными, разделёнными хотя бы одним согласным
В узлах какие-то условные переменные, главное - связи между узлами
Разрешены петли. Петли означают повторение много раз, что в регулярных
выражениях соответствует звёздочке *

48. Нарисуйте конечные автоматы для слогов

1) для закрытого слога
2) для слова с 2 гласными, разделёнными хотя бы одним согласным

49. Регулярки в ELIZA

50. Регулярки в ELIZA

51. Нормализация текстов

1)
2)
3)
4)
Токенизация
Удаление стоп-слов
Приведение к начальной форме / лемматизация / нормализация
Разделение на предложения

52. Токенизация и стоп-слова

1) Удалить знаки препинания, хештеги, смайлики и прочую ненужную
ерунду
2) Поделить по пробелам (смотри картинку)
3) Удалить стоп-слова
и, в, во, не, .. .. .., более, всегда, конечно, всю, между

53. Токенизация

54. Нормализация, лемматизация, стемминг…

В чём разница?
Токенизация и нормализация слов делаются методом каскадов простых
регулярных выражений и/или с помощью конечных автоматов.

55. Byte-pair encoding для токенизации

● Не отталкивается от того, что является лингвистически словом в
конкретном языке (ура?)
Иногда нам хочется делить точно по пробелам и выделять слова типа
spinach, а иногда в том же тексте нам хочется что какая-нибудь более
длинная сущность тоже с пробелами внутри выделилась как слово: New
York Times. А иногда мы хотим выделять морфемы в отдельные слова.
+ можно учитывать редкие слова или новые слова, не встречающиеся в
корпусе
+ data compression - выгодно для экономии памяти

56. Byte-pair encoding для токенизации

С этим алгоритмом никакие слова не
будут забыты и не распознаны

57. Byte-pair encoding для токенизации

Словарь на входе с информацией по частотности слов

58. Byte-pair encoding для токенизации

Смотрим какая комбинация из двух символов самая частотная

59. Byte-pair encoding для токенизации

Снова ищем самую частотную пару символов уже в новом словаре

60. Byte-pair encoding для токенизации

И снова:

61. Byte-pair encoding для токенизации

Если мы дойдем до конца выйдет вот что:
Это наш словарь

62. Byte-pair encoding для токенизации

Что будет с каким-нибудь неизвестным нам ранее словом lower? Оно
токенизируется в два low + er.
И это супер-хорошо, потому что мы смогли отделить морфему!
Значит, и прочитать такой текст компьютер сможет, ведь у er есть
собственное значение

63. Домашнее задание (оцениваемое)

Напишите правила для своей ELIZA, но с каким-то другим концептом, не
психолога :)
● паттерн описанный регуляркой у собеседника + ответная реплика ELIZA
тоже описанная регуляркой. Помните, что \1 так обозначается
сгруппированная информация из сообщения собеседника. То, что у него
в скобочках (). Если скобочек в регулярке собеседника несколько, то
сгруппированную из них информацию в ответе ELIZA можно
последовательно обозначать \1, \2 и т.д.
Например:
Я: Мне очень грустно и я хочу есть = [Мм]не (.*) и я? хочу (.*)
ELIZA: Может, тебе очень грустно из-за того, что ты хочешь есть? = Может,
тебе \1 из-за того, что ты хочешь \2?

64. Всем спасибо

Напоминаю про задание мне можно писать сюда
Можно спрашивать туда же
Сдавать либо мне сюда, либо лично сдать бумажку (перед|после)
заняти(ем|я)
tg @annaklezovich
[email protected]

65. Литература

1.
2.
3.
4.
5.
6.
7.
Карахтанов Д. С. Реализация алгоритма Metaphone для кириллических фамилий средствами языка PL/SQL //
Молодой ученый. — 2010. — №8. Т. 1. — С. 162-168. — URL https://moluch.ru/archive/19/1967/ (дата
обращения: 29.01.2020).
https://habr.com/ru/post/114947/
https://web.stanford.edu/~laurik/publications/jnle-97/rele.pdf
http://courses.washington.edu/ling472/slides/0329.pdf
http://lpcs.math.msu.su/~pentus/mfk2015/Lecture05_20151007.pdf
Jurafski Speech Processing Book
Jurafski presentation on Noisy Channel