Разработка и исследование методов звукового поиска в базах данных на основе фонетического кодирования и их использование для ускорения распознавания речи тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Ду Цзяньмин

• Ду Цзяньмин
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Ду Цзяньмин

ВВЕДЕНИЕ

ГЛАВА 1. АЛГОРИТМ ФОНЕТИЧЕСКОГО КОДИРОВАНИЯ

1.1. Обзор алгоритмов фонетического кодирования

1.2. Алгоритм SoundEx

1.3. Другие производные алгоритмы

1.3.1. Алгоритм NYSIIS

1.3.2. Алгоритм Daith-Mokotoff SoundEx

1.3.3. Алгоритм Metaphone

1.4. Фонетическое расстояние

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

1.4.2. Расстояние на основе N-грамм

1.4.3. Расстояние Джаро

1.5. Исследование фонетических алгоритма русского языка

1.5.1. Алгоритм хеширования по сигнатуре

1.5.2. Алгоритм MetaphoneRu

1.5.3. Алгоритм Polyphone

1.5.4. Анализ важных характеристик русских слов

1.6. Выводы по первой главе

ГЛАВА 2. ТЕОРИЯ МЕТОДА ПОИСКА СЛОВ ДЛЯ

УСКОРЕНИЯ РАСПОЗНАВАНИЯ РЕЧИ

2.1. Обзор системы распознавания речи

2.2. Выбор набора инструментов для исследования

2.3. Скрытая Марковская модель в области распознавания речи

2.3.1. Обзор НММ

2.3.2. Архитектура системы распознавания речи на основе НММ

2.3.3. Развитие модели НММ

2.4. Теория поиска слов на основе фонетического кодирования

2.4.1. Проблемы поиска слов в словаре

2.4.2. Исследование фонем русского языка с помощью СМШрЫпх

2.4.3. Основная схема метода поиска слова

2.4.4. Функция «Аллофон» и его использование

2.4.5. Фонетический алгоритм и анализ результата последовательности фонем

2.4.6. Анализ правила и строения кодирования

2.5. Разработка метода звукового поиска слов в базах данных

2.5.1. Построение базы данных слов

2.5.2. Таблица перекодирования

2.5.3. Поиск из словаря и строение нового словаря

2.6. Применение

2.7. Выводы по второй главе

ГЛАВА 3. ЭКСПЕРИМЕНТЫ И РЕЗУЛЬТАТЫ

3.1. Модуль «поиск слов на основе фонетического

кодирования»

3.2. Эксперименты системы и анализ результатов

3.2.1. Эксперимент эффективности

3.2.2. Эксперимент правильности

3.3. Выводы по третьей главе

ОБЩИЕ ВЫВОДЫ И ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

Введение диссертации (часть автореферата) на тему «Разработка и исследование методов звукового поиска в базах данных на основе фонетического кодирования и их использование для ускорения распознавания речи»

Актуальность темы исследования.

В настоящее время технология электронного распознавания речи является одной из наиболее важных частей взаимодействия системы «человек -компьютер», статус устойчивого направления ведения научных исследований закрепился за ней еще с момента зарождения. В то же время с развитием информационных технологий распознавание речи находит все более широкие области применения. Можно без преувеличения сказать, что на сегодняшний день распознавание речи надолго закрепилось в повседневной жизни общества.

Многие технологические компании, такие как IBM, Microsoft, Apple, Google, Яндекс, iFlytex и т. д., постоянно исследуют и строят свои речевые информационные системы, например, чтобы установить расписание и отправить электронные письма, для использования голоса вместо ручного ввода навигационных адресов и так далее.

Теперь точность распознавания речи на малых и средних словарях очень высока. В августе 2017 года точность системы распознавания английской речи из Microsoft в определенной среде достигла уровня человеческой диктовки. Это является отличным результатом, но эта технология еще долека от идеальной.

В области речевых технологий существует ряд проблем. Например, из-за различных характеристик речи каждого человека распознавание речи независимых дикторов очень сложно, и при сильном шуме, многоязычии, большом словаре и т. д. технология распознавания речи нуждается в серьезном улучшении.

Для решения этих проблем необходимы совместные исследования в трех областях. Первая - математическая область. Сложные математические формулы и статистика больших данных являются основанием улучшенной технологии.

Вторая - область лингвистики и акустики. Изучение естественного языка играет важную роль в распознавании речи и семантики. Третья - область технологии компьютеров.

Процесс распознавания речи представляет собой поиск точных совпадений имеющихся в базе данных записей с предоставленным пользователем образцом, обработанным посредством серии вычислительных операций преобразования речевых сигналов.

По мере развития технологий в системах распознавания начали применяться методы цифровой обработки сигналов, статистического и вероятностного моделирования, такие как скрытые марковские модели (СММ) и искусственные нейронные сети (ИНС). В последние годы представлены значительные достижения в исследованиях алгоритма распознавания с использованием обоих приведенных методов.

В то время как с улучшением алгоритма скорость распознавания увеличивается, система распознавания становится более сложной. В частности, в случае больших словарей как нейронная сеть, так и скрытые марковские модели сталкиваются с проблемой огромных и медленных вычислений, особенно в русском языке, который обладает большим лексиконом и гибким языком, система распознавания речи не достигает качества аналогичной системы для английского языка.

Поэтому решение вопроса, как улучшить систему для русского языка, становится основным направлением исследований в России. Большая часть исследований в настоящее время направлена на увеличение скорости распознавания путем использования распределенной обработки, увеличения вычислительной скорости на основе аппаратурного ускорения. Например, Google использует огромную вычислительную сеть для ускорения распознавания речи. Фактически немалая часть времени распознавания речи тратится на поиск слов в словаре и поиск алгоритмом лучшего пути. Однако,

насколько нам известно, нет такого исследования, которое помогало бы оптимизировать использование словарей.

Процесс распознавания речи представляет собой поиск точных совпадений имеющихся в базе данных записей с предоставленным пользователем образцом, обработанным посредством серии вычислительных операций преобразования речевых сигналов.

Алгоритмы фонетического кодирования имеют возможность становления другого решения этой проблемы. Алгоритмы фонетического кодирования представляют собой алгоритмы поиска слов по их звучанию, которые широко используются в областях, где требуется сопоставление акустических данных с текстовыми образцами, например, для проверки написания и исправления слов, для поиска в базах данных, при добыче полезных ископаемых и т. д. Хотя эти алгоритмы не могут отдельно использоваться в области распознавания речи, они могут служить для улучшения поиска слов из словаря как предварительного процесса, чтобы ускорить скорость распознавания речи.

Цели и задачи. Цель диссертационной работы заключается в разработке и исследовании методов звукового поиска в базах данных на основе фонетического кодирования для ускорения распознавания речи на большом словаре.

Для достижения данной цели были поставлены и решены следующие задачи:

1) разработка фонетических алгоритмов для ускорения поиска слов в базах данных;

2) разработка метода фонетического кодирования для последовательности фонем языка;

3) реализация распознавания речи при использовании разработанного метода поиска слов в базах данных на основе алгоритма фонетического кодирования и определение ее эффективности.

Объект и предмет исследования. Объектом исследования является поиск слов в базах данных. Предмет исследования - метод звукового поиска слов в базах данных при распознавании речи.

Методы исследования. Методы акустического моделирования, распознавания речи, статистической обработки результатов экспериментов, методы поиска данных.

Реализация результатов. Основные результаты реализованы в виде модуля в системе распознавания речи СМШрЫпх, что ускорило процесс поиска отдельных слов в базах данных.

Достоверность результатов. Достоверность метода была подтверждена вычислительным экспериментом.

Научная новизна. Разработаны и исследованы следующие методы:

1) предложено использование фонетических алгоритмов для поиска слов в базах данных, отличающееся тем, что кодированию подвергается не последовательность букв слова, а последовательность его фонем;

2) разработан алгоритм фонетического кодирования для последовательности фонем русского языка, позволяющий находить близкие по произношению слова;

3) разработан и опробован эффективный метод поиска слов в базах данных на основе предложенного алгоритма фонетического кодирования.

Практическая значимость работы. Применение разработанного метода поиска слов на основе фонетического кодирования позволяет улучшить количественные и качественные характеристики современных систем распознавания слитной речи на большом словаре.

Положения, выносимые на защиту:

1) использование разработанных фонетических алгоритмов для ускорения поиска слов в базах данных;

2) алгоритм фонетического кодирования для последовательности фонем русского языка;

3) метод поиска слов в базах данных на основе алгоритма фонетического кодирования.

Апробация работы. Основные результаты работы были изложены в докладах и получили положительную оценку на следующих конференциях и научных семинарах

1) научный семинар кафедры «Информационные системы и телекоммуникации» МГТУ им. Н. Э. Баумана (Москва, 2017, 2018);

2) научный семинар Института проблем управления РАН (Москва, 2018);

3) международная научная конференция «Распределенные компьютерные и телекоммуникационные сети (ОСС^Ы)» (Москва, 2018);

4) молодежная научно-техническая конференция «Студенческая весна» МГТУ им. Н. Э. Баумана (Москва, 2014, 2016).

Публикации. Результаты диссертационной работы отражены в 6 научных статьях общим объемом 2,93 п.л., в том числе в 3 публикациях в изданиях из перечня ВАК РФ.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы. Объем работы составляет 1 12 печатных страниц, включает 12 рисунков и 25 таблиц. Библиография содержит 102 наименования.

Содержание работы

Во введении обоснованы важность и актуальность темы диссертации, сформулированы цель работы, а также основные задачи, которые необходимо решить для ее достижения, охарактеризованы научная новизна и практическая ценность работы, кратко изложены основные теоретические и практические результаты работы.

В первой главе представлен обзор теории алгоритма кодирования фонем. Приведено фонетическое исследование для русского языка.

Во второй главе представлен обзор системы распознавания речи, сделан выбор набора инструменты экспериментов. Далее изложены теория, метод поиска слов, проанализированы правила последовательности результата, описано применение этого метода.

В третьей главе описывается создание нового модуля, основанного на материалах второй главы, и разработаны эксперименты. Описывается экспериментальный процесс. Приведено сравнение результатов с аспектами эффективности и правильности между модифицированной системой и существующей системой.

В заключении приведены основные научно-технические достижения, полученные в процессе работы.

ГЛАВА 1. АЛГОРИТМ ФОНЕТИЧЕСКОГО КОДИРОВАНИЯ

1.1. Обзор алгоритмов фонетического кодирования

Алгоритмами фонетического кодирования являются алгоритмы, которые индексируют слова по их звучанию и преобразуют их в кодирующие тексты в виде кода, ключа или индекса [21] на основе последовательности букв слова и правил произношения. Если закодированные тексты двух различных слов совпадают или близки, можно сделать вывод, что слова близки по звучанию.

Первым представителем алгоритмов фонетического кодирования является алгоритм SoundEx [11], который использовался в 1930-х годах для кодирования фамилий английского языка при переписи населения. Этот алгоритм использует метод кодирования для устранения орфографических и типографских ошибок в именах. Например, для таких английских слов, как «Smith», «Smithe» и «Smyth», этот алгоритм вычислит одинаковый кодированный текст «S530», т. е. алгоритм отождествит эти слова как звучащие одинаково.

С появлением и развитием компьютерных технологий появилось много других алгоритмов фонетического кодирования, в том числе и для различных естественных языков. Примеры этих алгоритмов включают в себя алгоритмы Metaphone [12], NYSIIS [13], модифицированный SoundEx, улучшенный SoundEx [14] и др.

Алгоритмы фонетического кодирования используются не только для сравнения слов, но также для определения расстояния между словами при звуковом поиске. На практике наиболее широко используемые алгоритмы для получения расчета расстояний: Джаро [16] и расстояния Левенштейна [15], а также расстояния на основе модели N-грамм [18].

Алгоритмы фонетического кодирования широко используются в областях, где необходимо сравнивать акустические данные с текстовыми образцами, например, для проверки правописания и исправления слов, для поиска в базах данных, для распознавания речи, при добыче полезных ископаемых, для идентификации пользователей, для кодирования речи на разных языках, для поиска в сети Интернет и т. д.

Несмотря на появление и развитие модифицированных моделей и методов распознавания речи, таких как вероятностные и скрытые марковские модели, нейронные сети, машинное обучение и др., алгоритмы фонетического кодирования не утратили своей актуальности, так как являются базовыми для применения этих моделей и методов на практике [19, 20].

1.2. Алгоритм SoundEx

SoundEx для кодирования английского слова состоит из 5 шагов [23]:

1. Не кодировать первую букву слова и сохранить его.

2. Из слова удалять гласные A, E, I, O, U и незвуковые буквы Y, W и H.

3. Согласно таблице 1 кодировать оставшиеся буквы на цифры.

4. Если код содержит группу из одинаковых цифр, то сохранить только первую цифру.

5. Результирующий код генерируется из первой буквы слова и ещё трех первых цифр, полученный на предыдущих шагах. Если код меньше трех цифр, добавить код с нулями.

Пример 1. Используя приведенный выше алгоритм, мы получаем кодированный текст «L000» для английского слова «Lee» и получаем текст «S000» для слова «Shaw».

Кодирование букв в алгоритме SoundEx

Цифра Буквы

1 B, P, F, V

2 C, S, K, G, J, Q, X, Z

3 D, T

4 L

5 M, N

6 R

Пример 2. Для пояснения шага 4 рассмотрим слово «Ashcroft». В связи с наличием шага 4 кодированный текст слова будет «A226» вместо «A261» для этого слова.

Из таблицы 1 видно, основной принцип кодирования букв заключается в том, близкие буквы по звучанию кодируются с одинаковой цифрой, а удаляют непроизносимые буквы. Но этот алгоритм не свободен от недостатков.

Первый недостаток состоит в том, что есть близкие по звучанию слова, но они имеют неодинаковые кодирующие тексты.

Пример 3. Слово «Leigh» и слово «Lee» имеют одинаковое произношение, но получаем разные кодирующие тексты: «L200» и «L000» соответственно.

Обратный первому второй недостаток: есть разные звуковые слова с одинаковым текстом кода.

Пример 4. Слова «Ghosh» и «Gauss» имеют разное произношение, но их кодирующие тексты одинаковые: «G200».

Чтобы частично устранить эти проблемы, возникающие во время работы алгоритма, в настоящее время на английском языке используются модифицированные алгоритмы SoundEx со следующей таблицей кодирования.

Кодирование букв в модифицированном алгоритме

Цифра Буквы

1 В, Р

2 Б, V

3 С, Б, К

4 а, I

5 0, х, ъ

6 Б, Т

7 ь

8 М, N

9 Я

Из таблицы 2 видно, что из группы букв 1 и 2 исходного алгоритма БоипёЕх образованы новые группы со своим цифровым кодом. Кроме того, длина кодирующего текста в этом модифицированном алгоритме кодирования не ограничивается четырьмя кодами.

Эксперименты показали, что одно значение кода БоипёЕх может содержать до 21 фамилии. Модифицированный алгоритм БоипёЕх имеет только две или три таких фамилии.

Известно, что алгоритм БоипёЕх сильно зависит от языка. Разные языки должны разработать разные группы, поэтому многие модификаций алгоритма БоипёЕх были разработаны для различных языков: например, для испанского языка [25], китайского языка [24], персидского языка [26] и т.д.

Для русского языка используются буквы в соответствии с таблицей 3, и удаленные буквы - это гласные: А, И, У, Э, О, Е, Ы, Я, Ю, Ё и знаки Ъ и Ь.

Несмотря на свои недостатки, алгоритм SoundEx имеет положительные отзывы [11].

Кодирование букв в алгоритме SoundEx для русского языка

Цифра Буквы

1 Б, П

2 Ф, В

3 Ж, З, С, Х

4 К, Г,

5 Ц, Ч, Ш, Щ

6 Д, Т

7 Л, Й

8 М, Н

9 Р

В настоящее время этот алгоритм широко используется для сравнения слов и идентификации слов по звучанию, и вероятность результатов значительно повышается.

Благодаря его простоте и низкой вычислительной сложности, алгоритм SoundEx уже стал стандартным алгоритмом поиска в почти всех известных систем управления базами данных[27].

1.3. Другие производные алгоритмы 1.3.1. Алгоритм NYSIIS

Алгоритм NYSIIS был разработан в 1970 году. Этот алгоритм использован в одноименной информационной системе «New York State Identification and Intelligence System» [13]. Этот алгоритм использует более сложные правила для преобразования исходных слов и обеспечивает несколько лучшие результаты кодирования по сравнению с алгоритмом SoundEx.

Этот алгоритм учитывает произношение слов на английском языке и состоит из шести шагов:

1) Заменить префикс преобразования (начала слова) следующими подстановками: MAC ^ MCC; K ^ C; KN ^ N; PF, PH^ FF; SCH ^ SSS.

2) Заменить суффикс (конец слова) следующими подстановками: DT, RD, RT, NT, ND ^ D; EE ^ Y; IE ^ Y.

3) Заменить слова в целом следующими подстановками: A, E, I, O, U ^ A; EV ^ AF; K ^ C; KN ^ N; M ^ N; PH ^ FF; Q ^ G; SCH ^ SSS; W ^ A; Z ^ S.

4) Удалить H, который стоит после гласных, и удалить A, S, которые находятся в конце слова.

5) Заменить суффикс слова подстановкой: AY ^ Y.

6) Ограничить полученный код до 6 символов.

Как видно из описания шагов NYSIIS, этот алгоритм использует большое количество правил, связанных с написанием и произношением. Алгоритм также рассматривает функцию гласных звуков в произношении, алгоритм заменяет все гласные гласной A.

Сравнительное исследование алгоритмов кодирования показало, что алгоритм NYSIIS лучше всего подходит для кодирования фамилий английского языка, которые обеспечивают отличные результаты.

Пример 5. Английские фамилии «Brain», «Brown» и «Brun» имеют одинаковый кодирующий текст «Bran». Фамилии «Capp», «Cope» и «Kipp» получают кодирующий текст «Cap». Для близких фамилий «Dane», «Dean» и «Dionne» есть код «Dan» [27].

1.3.2 Алгоритм БаИ;еЬ-Моко1;о11 8ои^Ех

В процессе использования алгоритмов фонетического кодирования установлено, что SoundEx и NYSIIS не слишком хорошо работают со словами на других языках. Чтобы учесть особенности произношения слов в других языках, разработан алгоритм Daitch-Mokotoff SoundEx, названный в честь автора. Этот алгоритм улучшает SoundEx с использованием большей длины кода, улучшает различные произношения слов, которые выражаются в нескольких вариантах кодирования одного и того же слова.

Кодирование букв в алгоритме ВайсЬ-Моко1^ ЗоидёЕх

Последовательность букв Н Г О

А1, Л1, ЛУ, Е1, Е1, БУ, Ш, Ш, иУ, 01, 01, ОУ 0 1 -

ли 0 7 -

1А, 1Е, 10, 1и 1 - -

Еи 1 1 -

А, Е, I, О, и, иЕ, У 0 - -

I 1 1 1

БТСИ, ЗТБСИ, ЗСИТБСИ, БСИТБИ, БСИТСИ, БИТБИ, БИТСИ, БИСИ, БТ^, БТЯБ, БТБИ, Б/СБ 2 4 4

ББ, БСИТ, БСИБ, БИТ, БТ, БИБ, Б/Б, БП 2 43 43

СБ/, С/Б, СБ, С/, Б^, БЯБ, ББИ, ББ, Б/И, Б/Б, Б/, ТС, ТСИ, ТБ, Т/, Т^, ТЯБ, ТЯСИ, ТБИ, ТТБ/, ТТ/, ТТБ, Т/Б, ТБ/, ТТСИ, ТТБСИ, Б/, БСИ, БИ, /БСИ, 7ШИ, /И, /Б 4 4 4

БС 2 4 4

Б, БТ, Т, ТИ 3 3 3

X, СИБ, КБ 5 54 54

Б, / 4 4 4

С, си, ск, а, к, ки, о 5 5 5

И 5 5 -

М, N 6 6 6

КМ, MN 66 66 66

В, Б, БВ, Р, РИ, РБ, V, 7 7 7

Ь 8 8 8

Я 9 9 9

Алгоритм Daitch-Mokotoff имеет более сложные правила для преобразования слов в их код. Как и в алгоритме NYSIIS, с формированием кодирующих текстов не только участвуют отдельные буквы, но и их последовательность. В соответствии с таблицей 4 [14] осуществляются преобразования слова в числовые коды.

В таблице 4 показан порядок преобразований, который соответствует порядку последовательностей букв. Столбцы Н, Г и О указывают цифровые коды для букв из первой столбца: Н - это последовательность букв в начале слова, Г -перед гласной буквой, и О - в других случаях.

Альтернативные коды слова, которые учитывают различные произношения слов, получаются для слов, образованных из исходного следующими подстановками: K, TZ ^ C; TCH, KH ^ CH; TSK ^ CK; Y, DZH ^ J; RTZ, ZH ^ RS.

Пример 6. При использовании алгоритма Daitch-Mokotoff получаем два кода для имени «Peters», которое имеет код SoundEx «Р362», 739400 - для произношения «Peters» и 734000 - для произношения «Petertz». Имя «Jackson», которое имеет код SoundEx «J250», получает четыре кода Daitch-Mokotoff: 145460, 154600, 445460, 454600 для произношений «Jakson», «Jackson», «Jatskon» и «Yakson» соответственно.

1.3.3 Алгоритм Metaphone

Metaphone - это еще один алгоритм фонетического кодирования слов, основанный на их произношении, который учитывает основные правила английского языка. Этот алгоритм был разработан в 1990 году [12]. Он отличается от предыдущих алгоритмов тем, что в нем реализованы более сложные правила преобразования. Другое отличие состоит в том, что буквы не сгруппированы и не

имеют цифрового кода. В результате алгоритм выдает код переменной длины, состоящий из букв.

Алгоритм имеет 16 шагов для английского языка [28]:

1) Удалить повторяющиеся соседние буквы, кроме буквы C.

2) Заменить префикс слова следующими подстановками: AE ^ E; GN ^ N; KN ^ N; PN ^ N; WR ^ R.

3) Удалить суффикс MB.

4) Заменить последовательности букв с буквой C следующими подстановками: C ^ K; CE ^ SE; CI ^ SI; CIA ^ XIA; CH ^ XH; CY ^ SY; SCH ^ SKH.

5) Заменить последовательности букв с буквой D следующими подстановками: D ^ T; DGE ^ JGE; DGI ^ JGY; DGY ^ JGY.

6) Заменить GH ^ H, если GH стоит не в конце слова и не перед гласной.

7) Заменить суффикс: GN ^ N и GNED ^ NED.

8) Заменить последовательности букв с буквой G следующими подстановками: G ^ K; GE ^ JE; GI ^ JI; GY ^ JY.

9) Удалить букву H после гласных, но не удалить его перед гласными.

10) Заменить префикс слова следующими подстановками: CK ^ K; PH ^ F; Z ^ S; Q ^ K; V ^ F.

11) Заменить последовательности букв с буквой S следующими подстановками: SIA ^ XIA; SIO ^ XIO; SH ^ XH.

12) Заменить последовательности букв с буквой T следующими подстановками: TCH ^ CH; TIA ^ XIA; TIO ^ XIO; TH ^ 0.

13) Заменить префикс WH ^ W. Если после буквы W нет гласной, удалить W.

14) Заменить префикс X ^ S, в середине слова - X ^ KS.

15) Удалить буквы Y, которые не находятся перед гласными.

16) Удалить все гласные, кроме начальной.

Пример 7. Код для фамилий «Brain», «Brown» и «Brun» - это «BRN», код «KP» - для фамилий «Capp», «Cope» и «Kipp», код «TN» - для фамилий «Dane», «Dionne» и «Dean», но фамилия «Dent» имеет различный код «TNT» (см. пример 5), код «SM0» - для фамилия «Smith», код «SXMT» - для фамилии «Schmit», но фамилия «Schmidt» имеет код «SXMTT», фамилии «Trueman», «Truman» имеют одинаковый код «TRMN».

В 2000 году была разработана вторая версия алгоритма, которая называлась Double Metaphone [29]. В отличие от его первой версии, которая была доступна только на английском языке, вторая версия учитывает особенности произношения слов, заимствованных из других языков [27]. Для этих слов результатом алгоритма являются два кода - по одному для каждого варианта произношения.

Хотя Double Metaphone имеет много преимуществ перед его первой версией алгоритма Metaphone, он тоже имеет некоторые ограничения [30]. В частности, также встречаются слова с различным произношением и одинаковыми кодом, например, фамилии «Ullos», «Elsa» и «Alice» имеют код «ALS».

В 2009 году появилась третья коммерческая версия алгоритма, которая называлась Metaphone 3. Этот новый алгоритм позволит повысить точность отождествления слов по произношению с 89 % - Double Metaphone, до 98 % -Metaphone 3 [32]. Metaphone 3 также начал поддерживать заимствованные слова из большего количества языков. Metaphone 3 очень сложен и содержит много правил. Описание алгоритма Metaphone 3 на языке Java требует более семи тысяч строк [31].

1.4. Фонетическое расстояние

Основным методом, реализуемым в рассмотренных разных алгоритмах фонетического кодирования, является метод преобразования эквивалентного слова в звуке, при котором часть слова, принадлежащая некоторому множеству

(эквивалентному классу), заменяется этом кодом множества или его типичным представителем [21].

В то же время стоит отметить, что части слов из одного множества частей слов, которые близкие по звучанию, также близки в письменном виде. Вводя соответствующую метрику в слово, можно поставить задачу определения сходства слов по произношению путем подсчета расстояния между словами по написанию.

Этот метод используется в другом типе алгоритмов фонетического кодирования, в котором при вычислении кода слова заменяются попарным сравнением слов с помощью вычисления расстояния между словами в определенном метрическом пространстве. Предполагается, что речевой и письменный строй тесно связаны друг с другом, осталось просто найти правильные соответствующие метрики.

Алгоритмы расстояния Левенштейна, расстояния на основе N-грамм и расстояния Джаро являются известными алгоритмами фонетического расстояния.

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

Известно [34], что более 80 % ошибок написания составляют ошибки перестановки букв. Поэтому расстояние Левенштейна в настоящее время определяется на четырех операциях: вставка, удаление, замена и транспозиция.

Суть расстояния Левенштейна - это мера разницы между двумя словами относительно минимального количества операций вставки, замены и удаления, необходимых для преобразования одного слова в другое [15].

Результат расстояния Левенштейна L (i, j) между двумя словами и w2 длины i и j по определению при min (i, j) = 0 равно max (i, j), а когда min (i, j) > 0, определяется из следующего рекуррентного уравнения:

L(i, j ) = min

'L(i, j -1) +1, L(i -1, j ) +1,

л

V

L(i -1, j -1) + m(i, j)

(1.1)

J

где т (i, j) равно нулю, если i-я буква слова а равна j-ой букве слова Ь, и единице - в противном случае.

1.4.2. Расстояние на основе N-грамм

N-грамм - это последовательность из N элементов (букв). Чтобы определить фонетическую близость двух слов, рассчитывается общее количество N-грамм. Обычно предполагается, что N равно З.

Пример 1. Рассмотрим два слова с одинаковым произношением: «Thompson» и «Thomson». Мы делим эти слова на З-граммы. В результате мы получим, что слово «Thompson» включает З-граммы «THO», «HOM», «OMP», «MPS», «PSO» и «SON», а слово «Thomson» - «THO», «HOM», «OMS», «MSO» и «SON». Общими 3-граммами этих слов являются «THO», «HOM» и «SON». Поэтому общая доля З-граммов составляет З/б.

Пример 2. Рассмотрим два слова: «Dean» и «Dane». Слово «Dean» имеет З-граммы «DEA» и «EAN», а слово «Dane» - «DAN» и «ANE». Хотя эти два слова имеют одинаковое произношение, они не имеют одинаковые З-граммы.

Как видно из примеров, различие между расстоянием, определенным с использованием З-граммов, и расстоянием Левенштейна состоит в том, что разные буквы имеют значительное влияние на первое расстояние и имеют слабое влияние на второе. Очевидно, что вычисление расстояния между словами на основе N-граммы позволяет получить лучший результат для более длинных слов, чем для коротких.

В целом К-граммы используются для сравнения нечетких слов, которое не затрагивает фонетических аспектов, например, для идентификации языка, так как каждый язык имеет свое собственное распределение К-граммов на достаточно длинных текстах, для сжатия текстов, для «угадывания» следующих букв и т. п. Другое использование К-грамма - индексирование данных в поисковых системах [24].

1.4.3. Расстояние Джаро

Неформальным определением расстояния Джаро между двумя словами является минимальное количество однобуквенных изменений, которое необходимо выполнить для преобразования одного слова в другое [17, 16]. Чем меньше расстояние, тем более походящими являются слова в сравнении.

Расстояние Джаро D (а, Ь) между двумя словами а и Ь при т > 0 определяется следующей формулой:

7Ч m m m-1 D(a, b) = w — + W2 — + W3-

a

b

m

(1.2)

где wl, w2, и w3 - весовые коэффициенты, wl + w2 + w3 = 1; m - число совпадающих букв (число букв, разнесенных не более чем на половину длины самого короткого слова); t - половина числа транспозиций (половина числа совпадающих букв, отличающихся порядковыми номерами). При m = 0 по определению D (a, b) = 0.

Список литературы диссертационного исследования кандидат наук Ду Цзяньмин, 2020 год

СПИСОК ЛИТЕРАТУРЫ

1. Xiong W., Droppo J., Huang X. The Microsoft 2016 conversational speech recognition system // ICASSP IEEE. New Orleans. USA. 5-9 March 2017. P. 5255-5259.

2.BOURLARD H., MORGAN N. Connectionist Speech Recognition. A Hybrid Approach // The Kluwer International Series in Engineering and Computer Science. 1994. Vol. 247. Kluwer Academic Publishers, Boston. 280 p.

3. Gales M., Young S. The Application of Hidden Markov Models in Speech Recognition // Foundations and Trends in Signal Processing. 2007. Vol. 1. No. 3. P. 195-304.

4. Huang X. Spoken Language Processing: A guide to theory, algorithm, and system development / X.Huang, A.Acero, H.Hon - Prentice Hall, 2001. 931 p.

5. Jelinek F., Bahl L., Mercer R. Design of a linguistic statistical decoder for the recognition of continuous speech. // IEEE Transactions on Information Theory. 1975. Vol. 21 (3). P. 250-256.

6. Juang B. H., Chou W., Lee C. H. Statistical and discriminative methods for speech recognition // A. J. R. Ayuso and J. M. L. Soler, editors, Speech Recognition and Coding - New Advances and Trends, 1995, Springer Verlag, Berlin. P. 109-132.

7. Mosle M. Accelerating Speech Recognition Algorithm with Synergic Hidden Markov Model and Genetic Algorithm Based on Cellular Automata // International Conference on Signal Processing Systems. 2009. P. 3-8.

8. Yu L., Ukdave Y., Kaeli D. GPU-accelerated HMM for Speech Recognition // Parallel Processing Workshops. 2014. P. 395-403.

9. Tian C., Liu J., Peng Z.M. Acceleration Strategies for Speech Recognition Based on Deep Neural Networks //Applied Mechanics & Materials. 2014. P. 5181-5185.

10.Viterbi A. J. Error bounds for convolutional codes and asymptotically optimum decoding algorithm // IEEE Transactions on Information Theory. 1982. Vol. 13. P. 260-269.

11. Knuth D.E. The Art of Computer Programming. Vol. 3. Second Editing. Addison-Wesley. 1998. P. 640.

12. Lawrence P. Hanging on the Metaphone // Computer Language. 1990. Vol. 7, No. 12. P. 12-25.

13. Taft R.L. Name Search Techniques // New York State Identification and Intelligence system: Special Report No. 1. New York: Albany, 1970. 118 p.

14. Soundexing and Genealogy by Gary Mokotoff. URL: http://www.avotaynu.com/soundex.htm (дата обращения: 08.09.2017).

15. Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов //Докл. АН СССР. 1965. Вып. 163 (4). С. 845-848.

16. Jaro M.A. Unimatch A computer system for generalized record linkage under conditions of uncertainty // Spring Joint Computer Conference. Anaheim. USA December 5-17. 1972. P. 523-530.

17. Jaro M.A. Advances in record-linkage methodology as applied to matching the 1985 census of Tampa. Florida // Journal of the American Statistical Association. 1989. No 84 (406). P. 414-420.

18. Jurafsky D., Martin J.H. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Pearson Prentice Hall. 2009.988 p.

19. Calculate Levenshtein distance between two strings. URL: http://php.net/manual/en/function.levenshtein.php (Дата обращения: 08.09.2017).

20. Hu B. On Capturing Semantics in Ontology Mapping // LLC: Springer Science + Business 2008. Vol. 11. P.361-385.

21. Выхованец В.С., Ду Цзяньмин., Сакулин С.А. Обзор алгоритмов фонетического кодирования // Управление большими системами. Выпуск 73. М.: ИПУ РАН. 2018. С.67-94.

22. Ван Л. Петросян О. Г. Ду Цзяньмин. Распознавание лиц на основе дерева коэффициентов для трехмасштабного вейвлет преобразования // Проблемы информационных безопасности. Компьютерные системы. 2018. №3. С. 126136.

23. Russell R.C, Margaret K.O. US Patent 1262167. 1435663. 1918. 1922.

24. Li D., Peng D. Spelling Correction for Chinese Language Based on Pinyin-Soundex Algorithm // Int. Conference on Internet Technology and Applications. Wuhan. China. August 16-18.2011. P. 1-3.

25. Angeles M.P., Espino-Gamez A., Gil-Moncada J. Comparison of a Modified Spanish Phonetic, Soundex, and Phonex coding functions during data matching process // Int. Conference on Informatics, Electronics & Vision. Fukuaka. Japan. June 15-18.2015. P. 1-5.

26. Kaveh-Yazdy F., Zareh-Bidoki A.M. Aleph or Aleph-Maddah, that is the question! Spelling correction for search engine autocomplete service // Int. Conference on Computer and Knowledge. Mashhad. Iran. October 29-30. 2014. P. 273-278.

27. Herzog T.N., Scheuren F.J., Winkler W.E. Data Quality and Record Linkage Techniques. New York: Springer. 2007. P. 115-121.

28. Binstock A., Rex J. Practical Algorithms for Programmers. Addison-Wesley. 1995. 577 p.

29. Lawrence P. The Double Metaphone Search Algorithm // C/C++ Users Journal. 2000. No. 18(6). P. 38-43.

30. Lisbach B., Meyer M. Linguistic Identity Matching // Springer Fachmedien Wiesbaden, 2013. P. 118-120.

31. Lawrence P. Metaphone 3: Version 2.1.3. URL: https://searchcode.com/codesearch/view/2366000/ (дата обращения: 18.02.2012).

32. Pande B.P., Dhami H.S. Application of Natural Language Processing Tools in Stemming // Int. Journal of Computer Applications. 2011. No. 27(6). P. 14-19.

33. Каньковски П. «Как ваша фамилия?» или русский MetaPhone // Программист. 2002. Вып. 8. С. 36-39.

34. Cherichi S., Faiz R. Upgrading Event and Pattern Detection to Big Data // International Conference on Computational Collective Intelligence. Springer International Publishing. 2016. P. 377-386.

35. Winkler W.E. String comparator metrics and enhanced decision rules in the Fellegi-Sunter model of record // Proc. of the Section on Survey Research Methods. American Statistical Association. 1990. P. 354-359.

36. Maarif H.A., Akmeliawati R., Htike Z.Z. Complexity Algorithm Analysis for Edit Distance // Int. Conference on Computer and Communication Engineering. Kuala Lumpur. Malaysia September 23-24. 2014. P. 135-137.

37. Бойцов Л.М. Использование хеширования по сигнатуре для поиска по сходству. Прикладная математика и информатика. М. Изд-во факультета ВМиК, МГУ 2000. № 7. С. 150-155.

38. Paramonov V.V., Shigarov A.O., Ruzhnikov G.M. et al. Polyphon: An Algorithm for Phonetic String Matching in Russian Language // Int. Conference on Information

and Software Technologiesro Druskininkairo ЫШиатаю October 13-15, 2016. Springer International РиЬШЫ^ю 2016. P. 568-579.

39. Kipyatkova I. Improving Russian LVCSR using deep neural networks for acoustic and language modelling//LECTURE NOTES IN COMPUTER SCIENCE. SpringerVerlag GmbH. 2018. P. 291-300.

40. Markovnikov N., Kipyatkova I., Lyakso E. End-to-end speech recognition in Russian // LECTURE NOTES IN COMPUTER SCIENCE. Springer-Verlag GmbH. 2018. P. 377-386.

41. Корсун О. Н., Габдразманов А. Ш. Новые алгоритмы распознавания речевых команд в рамках классического сравнения с эталонами // МОДЕЛИРОВАНИЕ АВИАЦИОННЫХ СИСТЕМ Сборник тезисов докладов. Председатель Организационного и Программного комитетов конференции Сергей Юрьевич Желтов. 2018. С. 262.

42. Korsun O.N., Poliyev A.V. Optimal pattern synthesis for speech recognition based on principal component analysis // Workshop on materials and engineering in aeronautics (MEA2017) 15-16 November 2017. Moscow. Russian federation. P. 012014

43. Чучупал В.Я. Моделирование вариативности произношения для уменьшения уровня ошибок при распознавании речи // Машинное обучение и анализ данных. 2014. Т. 1. № 9. С. 1168-1179.

44. Смирнов В. А., Гусев М. Н., Фархадов М. П. Функция модуля акустического моделирования в системе автоматического анализа неструктурированной' речевой информации // Управление большими системами. Выпуск 45. М.: ИПУ РАН. 2013. С.181-205.

45. About the Kaldi project. URL: http://kaldi-asr. org/doc/about.html (дата обращения: 17.02.2018).

46. Povey D., Ghoshal A. The KALDI Speech Recognition Toolkit// IEEE Workshop on Automatic Speech Recognition and Understanding. Hawaii. USA. December 11-15. 2011. P 102-110.

47. Soundex System The Soundex Indexing System. URL: https: //www. archives. gov/research/census/soundex.html (дата обращения: 30.05.2007)

48. Lamere P., Kwok P. The CMU Sphinx-4 speech recognition system// IEEE International Conference on Acoustics, Speech, and Signal Processing. Hong Kong. China. April 6-10. 2003.

49. AIMAN F., SAQUIB Z., NEMA S. Hidden Markov Model system training using HTK//International Conference on Advanced Communication Control and Computing Technologies. Ramanathapuram. India. May 25-27. 2016. P. 806-809.

50. CMU Sphinx Acoustic and Language Models. URL: https://sourceforge.net/proiects/cmusphinx/files/Acoustic%20and%20Language%20 Models/Russian (дата обращения: 07.05.2016).

51. Baum L. E., Eagon J. A. An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology //Bulletin of American Mathematical Society. Vol. 73. 1967. P. 360-363.

52. Evermann G., Chan H.Y., Gales M.J.F. Development of the 2003 CU-HTK conversational telephone speech transcription system // Proceedings of ICASSP. Montreal. Canada. 2004. P. 245-253.

53. Matsoukas S., Gauvain J.L., Adda A. Advances in transcription of broadcast news and conversational telephone speech within the combined EARS BBN/LIMSI system // IEEE Transactions on Audio, Speech and Language Processing. September 2006. Vol. 14. No. 5. P. 1541-1556.

54. Soltau H., Kingsbury B., Mangu L. The IBM 2004 conversational telephony system for rich transcription //Proceedings of ICASSP. Philadelphia. PA. 2005. P. 205-209.

55. Baker J. K. The Dragon system — An overview // IEEE Transactions on Acoustics Speech and Signal Processing. Vol. 23. No. 1. 1975. P. 24-29,

56. Jelinek F. Continuous speech recognition by statistical methods // Proceedings of IEEE. Vol. 64. No. 4. 1976. P. 532-556.

57. Lowerre B. T. The Harpy Speech Recognition System / PhD thesis. Carnegie Mellon. 1976. 262 p.

58. Juang B.H. On the hidden Markov model and dynamic time warping for speech recognition — A unified view // AT and T Technical Journal. Vol. 63. No. 7. 1984.P. 1213-1243.

59. Juang B.H. Maximum-likelihood estimation for mixture multivariate stochastic observations of Markov chains // AT and T Technical Journal. Vol. 64. No. 6. 1985. P. 1235-1249.

60. Levinson S. E., Rabiner L. R., Sondhi M. M. An Introduction to the application of the theory of probabilistic functions of a Markov process to automatic speech recognition // Bell Systems Technical Journal. Vol. 62. No. 4. 1983. P. 1035-1074.

61. Rabiner L.R. A tutorial on hidden Markov models and selected applications in speech recognition // Proceedings of IEEE. Vol. 77. No. 2. 1989. P. 257-286.

62. Jelinek F. A discrete utterance recogniser // Proceedings of IEEE. Vol. 73. No. 11. 1985. P. 1616-1624.

63. Rabiner L. R., Juang B.H., Levinson S. E., Sondhi M. M. Recognition of isolated digits using HMMs with continuous mixture densities // AT and T Technical Journal. Vol. 64. No. 6. 1985. P. 1211-1233.

64. Price P.J., Fisher W., Bernstein J., Pallet D.S. The DARPA1000-word Resource Management database for continuous speech recognition // Proceedings of ICASSP. vol. 1. New York. 1988. P. 651-654.

65. Young S. J., Chase L. L. Speech recognition evaluation: A review of the US CSR and LVCSR programmes // Computer Speech and Language. Vol. 12. No. 4. 1998. P. 263-279.

66. Pallet D. S., Fiscus J. G., Garofolo J. 1998 broadcast news benchmark test results: English and non-English word error rate performance measures // Tech. Rep. National Institute of Standards and Technology (NIST). 1998. P254-260.

67. Godfrey J. J., Holliman E. C., Mcdaniel J. Switchboard // Proceedings of ICASSP. San Francisco. USA. Vol. 1. P. 517-520. 1992.

68. Davis S. B., Mermelstein P. Comparison of parametric representations for monosyllabic word recognition in continuously spoken sentences // IEEE Transactions on Acoustics Speech and Signal Processing. Vol. 28. No. 4. 1980. P. 357-366.

69. Valtchev V., Odell J., Woodland P. C.A novel decoder design for large vocabulary recognition // Proceedings of ICSLP. Yokohama. Japan. 1994. P.195-200.

70. Young S. J., Russell N. H., Thornton J. H. S. Token passing: A sim- ple conceptual model for connected speech recognition systems // Tech. Rep. CUED/F-INFENG/TR38. Cambridge University Engineering Department. 1989. P. 100-124.

71. Young S. J., Russell N. H., Thornton J. H. S. The use of syntax and multiple alternatives in the VODIS voice operated database inquiry system // Computer Speech and Language. Vol. 5. No. 1. 1991.P. 65-80.

72. Ortmanns S., Ney H., And Aubert X. A word graph algorithm for large vocabulary continuous speech recognition // Computer Speech and Language. Vol. 11. No. 1. 1997. P. 43-72.

73. Odell J.J., Valtchev V., Woodland P.C. A one-pass decoder design for large vocabulary recognition // Proceedings of Human Language Technology Workshop. Plainsboro NJ. Morgan Kaufman Publishers Inc. 1994. P. 405-410.

74. Haeb-Umbach R., Ney H. Improvements in time-synchronous beam search for 10000-word continuous speech recognition // IEEE Transactions on Speech and Audio Processing. Vol. 2. 1994. P. 353-356.

75. Aubert X., Ney H. Large vocabulary continuous speech recognition using word graphs // Proceedings of ICASSP. Vol. 1. P. 49-52. Detroit. USA.1995.

76. Jelinek F. A fast-sequential decoding algorithm using a stack // IBM Journal on Research and Development. Vol. 13. 1969. P.675-685.

77. Paul D. B. Algorithms for an optimal A* search and linearizing the search in the stack decoder // Proceedings of ICASSP. Toronto. 1991. P. 693-996.

78. Mohri M., Pereira F., Riley M. Weighted finite state transducers in speech recognition // Computer Speech and Language. Vol. 16. No. 1. 2002. P. 69- 88.

79. Richardson F., Ostendorf M., Rohlicek J.R. Lattice-based search strategies for large vocabulary recognition // Proceedings of ICASSP. Detroit. Vol. 1. 1995. P. 576-579.

80. Thompson H. Best-first enumeration of paths through a lattice — An active chart parsing solution // Computer Speech and Language. Vol. 4. No. 3. 1990.P. 263- 274.

81. Young S. J. Generating multiple solutions from connected word DP recognition algorithms // Proceedings of IOA Autumn Conference. vol. 6. 1984. P. 351- 354.

82. Mangu L., Brill E., Stolcke A. Finding consensus among words: Lattice- based word error minimisation // Computer Speech and Language. Vol. 14. No. 4. 2000. P. 373400.

83. Evermann G., Woodland P.C. Posterior probability decoding, confidence estimation and system combination // Proceedings of Speech Transcription Workshop. Baltimore.2000. P 45-57.

84. Stolcke A., Brill E., Weintraub M. Explicit word error minimization in N-Best list rescoring // Proceedings of EuroSpeech. Rhodes. Greece, 1997. P 234-241.

85. Evermann G., Woodland P.C. Large vocabulary decoding and confidence estimation using word posterior probabilities // Proceedings of ICASSP. Istanbul. Turkey. 2000. P. 1655-1658.

86. Fiscus J. A post-processing system to yield reduced word error rates: Recogniser output voting error reduction (ROVER) // Proceedings of IEEE ASRU Workshop. Santa Barbara. 1997. P. 347-352.

87. Goel V., Kumar S., Byrne B. Segmental minimum Bayes-risk ASR voting strategies // Proceedings of ICSLP. Beijing. China. 2000. P.139-142.

88. Hakkani-Tur D., Bechet F., Riccardi G. Beyond ASR 1-best: Using word confusion networks in spoken language understanding // Computer Speech and Language. Vol. 20. No. 4. October 2006. P. 495-514.

89. Скрипник Я.Н., Смоленская Т.М. Фонетика современного русского языка: учебное пособие. Ставрополь: Изд-во СГПИ [Под ред. Я.Н. Скрипник]. 2010. 152с.

90. Canford J.C. A Practical Introduction to Phonetics / Oxford University Press. 1988. 161 p.

91. Fogerty D., Humes L. E. The role of vowel and consonant fundamental frequency, envelope, and temporal fine structure cues to the intelligibility of words and sentences // The Journal of the Acoustical Society of America. Vol. 131. No. 2. 2012. P.1490-1501

92. Ladegorged P. Vowels and Consonants: An Introduction to the Sounds of Languages / Oxford: Blackwell - 2001 - P. 191

93. Mendis C., Droppo J Parallelizing WFST speech decoders// IEEE International Conference on Acoustics, Speech and Signal Processing. Shanghai. China. March 2025. 2016. P. 5325-5329.

94. Allauzen C., Riley M., Shalkwyk J.. Openfst: A General and Efficient Weighted Finite-State Transducer Library // International Conference on Implementation and Application of Automata. Praque. Czech Republic. July 16-18. 2007. P. 11-23.

95. Mohri M., Pereira F., Riley M. Weighted finite-state transducers in speech recognition. // Computer Speech & Language. Vol. 16. Issue 1. January 2002. P. 6988.

96. Josef R. Novak, Nobuak M., Hirose K. Dynamic Grammars with Lookahead Composition for WFST-based Speech Recognition //13th annual conference of the International Speech Communication Association. Portland. USA. September 9-13. 2012 P. 1079-1082.

97. Hori T. Nakamura A. Generalized fast on-the-fly composition algorithm for WFST-based speech recognition // 9th European Conference of Speech Communication and Technology. Lisbon. Portugal. September 4-8. 2005. P.1685-1688.

98. Выхованец В.С., Ду Цзяньмин., Назарова С. И. Контекстное распознавание слитной речи // Материалы VII-й Международной конференции «Управление развитием крупномасштабных систем» (MLSD'2013). Том II. М.: ИПУ РАН, 2013. С. 312-315.

99. Выхованец В.С., Ду Цзяньмин. Отложенная слоговая сегментация при распознавании слитной речи // Речевые технологии. 2016. № 1-2. С.45-54.

100. Dempster A., Laird N. Rubin D. Maximum likelihood from incomplete data via the EM algorithm // J. Royal Stat. Soc. 1977. Vol. 39. P. 1-38.

101. Reynolds D.A., Rose R.C. Robust test-independent speaker identification using Gaussian mixture speaker models. IEEE Transactions on Speech and Audio Processing. 1995. No. 3(1). P. 72-83.

102. Ду Цзяньмин. Выборочное распознавание фонем с помощью смеси Гауссовых распределений // Молодежный научно-технический вестник. 2016. № 6. С.25.