Алгоритм поиска в компьютерных системах и базах данных
SEARCH ALGORITHM IN COMPUTER SYSTEMS AND DATABASES

Описание.
Алгоритм поиска в компьютерных системах и базах данных.
Область назначения изобретения
[0001] Настоящее изобретение относится к области сопоставления звуковой информации и текстовой информации или текстовой информации и текстовой информации и определения степени соответствия между ними.
Уровень техники
[0002] Сопоставление звуковой и текстовой информации является важной областью развития современной технологии. В простейшем случае сопоставление происходит с целью определения тождества содержания между информацией в виде акустического сигнала и текстовой информацией. Сопоставление такого рода соответствует текущему уровню техники и является компонентом современных систем распознавания речи.
[0003] Однако можно поставить вопрос и о сопоставлении, выявляющем отдельные виды сходства между в целом не тождественными по информационному содержанию звуковыми данными и текстовыми данными или текстовыми данными и текстовыми данными. Настоящее изобретение относится к одному из возможных видов такого сходства - к так называемому ритмическому сходству.
[0004] Ритмическое сходство предполагает, что каждый из наборов данных имеет определенный "ритм" и ритмы двух наборов данных могут соответствовать или не соответствовать друг другу. В случае сопоставления двух наборов текстовых данных ритм определяется языковыми и жанровыми свойствами этих наборов - например, ритмом стихотворения можно, огрубляя, считать его стихотворный размер. В случае сопоставления звуковых данных с текстовыми данными ритм текстовых данных определяется их языковыми и жанровыми свойствами, а ритм звуковых данных - частотными характеристиками и иными свойствами звуковой волны. Например, ритмом музыкального произведения можно считать его ритм в обыденном понимании этого слова.
[0005] Автоматическое определение ритмической структуры отдельно для звуковых данных соответствует текущему уровню техники и используется в системах распознавания музыки. Автоматическое определение ритмической структуры текстовых данных и соотнесение ритмических структур в парах «текстовые данные - текстовые данные» и «текстовые данные - звуковые данные» является инновационным и до настоящего изобретения не производилось.
[0006] Другой инновационной чертой настоящего изобретения является механизм поиска. Он предусматривает индексацию баз звуковых и текстовых данных векторами, кодирующими ритмические свойства звуковых и текстовых данных, с последующей возможностью гибкого поиска по этим базам по отдельности или в сопоставлении друг с другом.
[0007] Технический результат заявленного изобретения заключается в обеспечении возможности подбора музыкальной и текстовой информации друг к другу на основании ритмических свойств.
Раскрытие сущности изобретения
[0008] Настоящее изобретение является механизмом для поиска ритмических соответствий между звуковой и текстовой информацией или текстовой информацией и текстовой информацией.
[0009] Основным механизмом поиска, охарактеризованный на фигуре 1, соответствий является поиск, то есть механизм обнаружения в базе данных ритмически похожих текстов. Поиск состоит из трех основных частей: механизма индексации базы текстов и музыкальных произведений; механизма ввода запроса; механизма поиска по индексу. Последняя часть получает на вход результат работы первых двух частей; первые две части работают независимо друг от друга. Далее эти части будут рассмотрены по очереди.
[0010] Первым компонентом настоящего изобретения является механизм индексации. Он применим как к текстовым данным, так и к звуковым данным.
[0011] Для индексации текстов, хранящихся в базе данных, система поиска вычисляет их ритмические характеристики - векторы вещественных чисел, кодирующие ритмические свойства отдельных строк текста и всего текста в целом. Каждое измерение такого вектора описывает степень того, насколько хорошо данный текст укладывается в одну из предопределенных ритмических схем.
[0012] Построение векторов происходит в два этапа. На первом этапе строка сегментируется на слоги, после чего в ней автоматически проставляются ударения; для этого используется модуль морфологического анализа. На выходе первого этапа строка закодирована с использованием особого метаязыка. А именно, в этой строке расставлены границы слогов и для каждого из них указано, ударный это слог, безударный или система не смогла однозначно определить его ударность.
[0013] На втором этапе система вычисляет сходство каждой строки с ритмическими схемами из предзаданного набора. Ритмические схемы задаются с помощью языка ритмико-метрических шаблонов, описанного в работе [1]. Примеры ритмико-метрического шаблона, соответствующего ямбу, и шаблона, соответствующего дольнику на трехсложной основе, приведены на фигуре. 2.
[0014] После того, как для каждой строки текста вычислен вектор, становится возможным вычислить агрегированный вектор для всего текста. Как правило, единый вектор для всего текста определяет его ритмическую структуру достаточно точно для успешного поиска, но для более тонкой настройки могут использоваться векторы отдельных строк.
[0015] После вычисления общей ритмической характеристики каждого текста (=агрегированного вектора для текста целиком), векторы всех текстов требуется сохранить в хранилище векторов, поддерживающем функцию поиска ближайших соседей (NearestNeighbourSearch), относящихся к каталогу музыкальной информации.
[0016] Для индексации музыкальных произведений их ритмические свойства должны быть введены в систему поиска одним из двух способов: или с помощью псевдотекста, содержащего сведения об ударениях, соответствующих сильным и слабым долям, или с помощью введения в систему мелодической линии музыкального произведения в виде звуковой записи, после чего алгоритм распознавания пения трансформирует эту запись в псевдотекст с проставленными ударениями. Полученные таким образом векторы помещаются в хранилище того же типа, что и стихотворные произведения, относящиеся к каталогу текстовой информации. Устройство механической индексации представлено на фигуре 3.
[0017] Второй составной частью поиска является механизм ввода поискового запроса. Ввод может быть осуществлен в текстовом или звуковом виде; при этом текстовый ввод запроса может соответствовать и интенции найти текстовые данные, подходящие к имеющимся у пользователя звуковым данным; в таком случае пользователь может ввести в систему псевдотекст, ритмически аналогичный исходным звуковым данным.
[0018] После этого по тексту с ударениями, автоматически проставленными системой морфологического анализа и затем при необходимости скорректированными пользователем, вычисляется ритмическая схема. Механизм ввода поиска представлен на фигуре 4.
[0019] Третьей составной частью системы поиска является механизм поиска по индексу. На вход ему поступает, с одной стороны, хранилище векторов, поддерживающее функцию поиска ближайших соседей (NearestNeighbourSearch) (за его построение отвечает первый компонент системы), а с другой - поисковый запрос в виде ритмической схемы (построенный вторым компонентом системы). Собственно поиск производится в два этапа и возможен в двух режимах: без учета тегов и метаинформации и с учетом тегов и метаинформации. Режим влияет на работу первого этапа поиска, но не влияет на работу второго. Вначале рассмотрим поиск без учета тегов, а затем с тегами.
[0020] На первом этапе осуществляется так называемый "грубый" поиск. А именно, для вектора текста запроса в ANN-хранилище ищется N наиболее похожих (близких) векторов, где N - заранее заданное число.
[0021] На втором этапе осуществляется точное ранжирование результатов грубого поиска, в процессе которого все тексты, возвращенные грубым поиском, поочередно сопоставляются с текстом запроса и определяется способ сопоставления строк двух текстов друг с другом, при котором суммарное расстояние между векторами сопоставленных строк является минимальным. Задача сопоставления строк возникает по той причине, что количество строк двух текстов может различаться. При сопоставлении строк учитывается их линейный порядок в текстах (сопоставление не может "путать" строки, т.е. никакой паре строк, идущих в некотором порядке в одном тексте, не может быть сопоставлена пара строк, идущих в другом порядке во втором тексте). Поиск сопоставлений может производиться с учетом логической структуры текстов (деления на припевы, куплеты и т.п.).
[0021а] Результатом поиска становится список пар "текст" - "музыкальный файл" или "текст" - "текст", упорядоченных в процессе убывания ритмического сходства. В случае задачи определения возможности спеть заданный текст на заданный музыкальный файл далее следует проверить, есть ли проверяемая пара "текст - файл" в этом списке и насколько высоко. В случае задачи поиска текста, подходящего для заданного музыкального файла или музыкального файла, подходящего для данного текста, следует взять первые несколько пар.
[0022] Поиск с учетом тегов представлен на фигуре 5. Тексты и музыкальные произведения могут быть снабжены тегами и метаинформацией. Теги - это слова и словосочетания из некоторого множества, описывающие стилистические и семантические свойства текста или музыкального произведения. Примеры тегов - «веселое», «о любви», «написано от первого лица», «джаз». Метаинформация - это формальные свойства текста или музыкального произведения. Примеры метаинформационных помет -«написано в 1876 году», «написано А.С. Пушкиным», «загружено в систему 19.08.2016 года». Поиск может проводиться с учетом как тегов, так и метаинформационных помет, причем возможен как И-поиск («веселое» и «о любви»), так и ИЛИ-поиск («веселое» или «о любви»). Для того, чтобы осуществлять поиск с учетом тегов, на первом этапе поиска необходимо скорректировать процедуру работы «грубого» поиска. А именно, N должно быть выбрано таким, чтобы в число N векторов вошло достаточное количество для фильтрации по тегам. Теги при этом могут быть встроены в систему хранения данных KDTree. Это позволит обойти проблему чрезмерного увеличения N с учетом редких тегов и, следовательно, чрезмерного увеличения объема памяти, необходимого для хранения промежуточных данных.
Краткое описание чертежей
[0023] На фигуре 1 показано устройство системы поиска в широком смысле.
[0024] На фигуре 2 показаны два примера ритмического шаблона - для ямба и для дольника.
[0025] На фигуре 3 показано устройство механизма индексации.
[0026] На фигуре 4 показано устройство механизма ввода запроса.
[0027] На фигуре 5 показано устройство механизма поиска в узком смысле.
Осуществление изобретения
В общем виде заявленный способ заключается в следующем.
[0028] Способ получения ритмических соответствий между музыкальной информацией и тестовой информацией в компьютерных системах и базах данных, включающий индексацию текстовой информации, ввод запроса и поиск по индексу, заключается в том, что для индексации базы текстов, хранящихся в базе данных, с использованием системы поиска вычисляют ритмические характеристики текстов, а именно векторы, кодирующие ритмические свойства отдельных строк текста и всего текста в целом, причем построение векторов системой поиска происходит в два этапа, на первом этапе строка сегментируется на слоги, после чего в строке автоматически проставляются ударения и на выходе первого этапа в строке текста расставлены границы слогов и для каждого из них указано, ударный это слог, безударный или система поиска не может однозначно определить его ударность, а на втором этапе система поиска вычисляет вектор для каждой строки текста, после чего вычисляет агрегированный вектор для всего текста, который определяет ритмическую структуру этого текста, затем агрегированный вектор сохраняют в хранилище векторов, поддерживающем функцию поиска ближайших соседей, после этого осуществляют ввод запроса в текстовом или псевдотекстовом виде для нахождения текстовых данных, подходящих звуковых данных, для чего осуществляют ввод запроса в виде текста или псевдотекста или в виде звуковой записи, которую алгоритм распознавания пения трансформирует в псевдотекст, а затем осуществляют поиск по индексу, для чего производится сопоставление, с одной стороны, векторов, имеющихся в хранилище, поддерживающем функцию поиска ближайших соседей, с другой стороны, вычисленного вектора для введенного текста или псевдотекста.
Поиск по индексу осуществляют в два этапа, на первом этапе производят грубый поиск, а именно в хранилище векторов ищут N наиболее похожих (близких) векторов, где N - заранее заданное число, на втором этапе осуществляют точное ранжирование результатов грубого поиска, в процессе которого все тексты, возвращенные грубым поиском, поочередно сопоставляют с текстом запроса и определяют способ сопоставления строк двух текстов друг с другом, при котором суммарное расстояние между векторами сопоставленных строк является минимальным. Способ получения ритмических соответствий между текстовой информацией и музыкальной информацией в компьютерных системах и базах данных, включающий индексацию музыкальной информации, ввод запроса и поиск по тексту, заключается в том, что длю индексации музыкальной информации, ее ритмические свойства вводят в систему поиска с помощью псевдотекста, содержащего сведения об ударениях, соответствующих сильным и слабым долям, или с помощью введения в систему мелодической линии музыкального произведения в виде звуковой записи, которую алгоритм распознавания пения трансформирует в псевдотекст с проставленными ударениями, и сохраняют в хранилище псевдотекстов, поддерживающем функцию поиска ближайших соседей, после этого осуществляют ввод запроса в виде текста, после чего по этому тексту с ударениями, автоматически проставленными системой морфологического анализа, вычисляют вектор, а затем осуществляют поиск по хранилищу псевдотекстов для нахождения подходящей музыкальной информации, для чего производят сопоставление, с одной стороны, псевдотекстов, имеющихся в хранилище, поддерживающем функцию поиска ближайших соседей, а с другой стороны, текста введенного запроса.
Осуществлением изобретения является веб-сервис поиска Musimatix. Он выполняет следующие функции: функцию поиска; функцию поиска по тегам; полнотекстовый поиск по текстам песен. Эти функции могут работать в комбинации, т.е. сервис может возвращать пересечение результатов поиска соответствующих видов.
При поиске музыкальной информации для текста способ получения ритмических соответствий между текстовой информацией и музыкальной информацией в компьютерных системах и базах данных, включает индексацию текстовой информации, являющейся базой текстов, ввод запроса и поиск по индексу. Для индексации базы текстов, хранящихся в базе данных, с использованием системы поиска вычисляют ритмические характеристики текстов, а именно векторы, кодирующие ритмические свойства отдельных строк текста и всего текста в целом. Причем построение векторов системой поиска происходит в два этапа, на первом этапе строка сегментируется на слоги, после чего в строке автоматически проставляются ударения и на выходе первого этапа в строке текста расставлены границы слогов и для каждого из них указано, ударный это слог, безударный или система поиска не может однозначно определить его ударность. На втором этапе система поиска вычисляет сходство каждой строки с ритмическими схемами из предварительно заданного набора для вычисления вектора для каждой строки текста, после чего вычисляет агрегированный вектор для всего текста, который является единым вектором для всего текста и определяет ритмическую структуру текста. Затем агрегированный вектор сохраняют в хранилище векторов, поддерживающем функцию поиска ближайших соседей. После этого осуществляют ввод запроса в текстовом виде для нахождения текстовых данных, подходящих звуковых данных. Для этого по тексту с ударениями, автоматически проставленными системой морфологического анализа, вычисляют ритмическую схему и осуществляют поиск по индексу, для чего производится сопоставление, с одной стороны, векторов, имеющихся в хранилище векторов, поддерживающее функцию поиска ближайших соседей, а с другой стороны вычисленной ритмической схемы.
При поиске текстовой информации для музыки способ получения ритмических соответствий между музыкальной информацией и текстовой информацией в компьютерных системах и базах данных включает индексацию музыкальной информации, ввод запроса и поиск по псевдотексту. Способ заключается в том, что для индексации музыкальной информации, ее ритмические свойства вводят в систему поиска с помощью псевдотекста, содержащего сведения об ударениях, соответствующих сильным и слабым долям, или с помощью введения в систему мелодической линии музыкального произведения в виде звуковой записи, которую алгоритм распознавания пения трансформирует в псевдотекст с проставленными ударениями, и сохраняют в специальном хранилище псевдотекстов, поддерживающем функцию поиска ближайших соседей. После этого осуществляют ввод запроса в виде псевдотекста или в виде звуковой записи, которую алгоритм распознавания пения трансформирует в псевдотекст, и осуществляют поиск по псевдотексту для нахождения подходящей текстовой информации, для этого производят сопоставление, с одной стороны, псевдотекстов, имеющихся в хранилище псевдотекстов, поддерживающее функцию поиска ближайших соседей, а с другой стороны, псевдотекста введенного запроса.
[0029] На большом массиве данных теги проставляются с помощью процедур автоматического текстового анализа и верифицируются посредством краудсорсинга. Помимо этого, авторы имеют возможность сами задавать тэги для собственных произведений.
[0030] Для сопоставления звуковым данным условных текстовых данных, которые потом могут быть использованы для поиска ("псевдотекста"), предполагается использование методов машинного обучения (в частности, глубоких нейронных сетей). В качестве обучающей выборки будут использоваться данные, полученные с помощью первой версии алгоритма ритмического поиска.
Промышленная применимость
[0031] Основным вариантом промышленного применения изобретения является онлайн-сервис создания песни, позволяющий пользователям осуществлять поиск по имеющейся базе данных и загружать в нее свои данные для индексации.
[0032] Другим вариантом промышленного применения является добавление возможности поиска к существующим базам данных - например, онлайн-библиотекам, текстовым базам данных поисковых систем, базам данных музыки и так далее.
[0033] Третьим вариантом является создание "рабочей среды" для музыкантов и поэтов, позволяющей им осуществлять поиск среди собственных музыкальных и текстовых файлов и, таким образом, упрощающей работу над песнями.