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

CTE(обобщенное табличное выражение) может ссылаться на себя, создавая рекурсивное CTE.
Рекурсивное CTE многократно выполняется, чтобы возвращать подмножество данных до тех пор, пока не получится конечный результирующий набор.
Обычно рекурсивные запросы используются для возвращения иерархических данных, например: отображение сотрудников в структуре организации или генерация последовательности.

Структура рекурсивного CTE

WITH cte_name (column_name [,...n]) AS (CTE_query_definition –- Anchor member is defined. UNION ALL CTE_query_definition –- Recursive member is defined referencing cte_name.) -- Statement using the CTE SELECT * FROM cte_name
CTE разбивается на закрепленный и рекурсивный элементы. Запускается закрепленный элемент с созданием первого вызова. Рекурсивный элемент ссылается на закрепленный и вызывается пока не вернет пустой набор.

Классический пример с сотрудниками

DECLARE @Employees TABLE (ID int NOT NULL, nvarchar(200) NOT NULL, ManagerID int NULL) INSERT INTO @Employees VALUES (1, N"Ken", NULL) ,(2, N"Brian",1) ,(3, N"Stephen", 2) ,(4, N"Michael", 2) ,(5, N"Linda", 3) ,(6, N"Syed", 4) ,(7, N"Lynn", 5) ,(8, N"David", NULL) ,(9, N"Mary", 8);
ManagerID - прямой руководитель.
В данном случае у нас два босса Ken и David, необходимо получить всех сотрудников отдела Кена.
WITH DirectReports (ID, , ManagerID, Level) AS (-- Anchor member definition SELECT e.ID, e., ManagerID, 0 AS Level FROM @Employees AS e WHERE e.ID = 1 UNION ALL -- Recursive member definition SELECT e.ID, e., e.ManagerID, Level + 1 FROM @Employees AS e INNER JOIN DirectReports AS d ON e.ManagerID = d.ID) -- Statement that executes the CTE SELECT ID, , ManagerID, Level FROM DirectReports

Прописные латинские буквы

Так же часто появляется необходимость в генерации различных последовательностей.
;WITH Letters AS(SELECT ASCII("A") code, CHAR(ASCII("A")) letter UNION ALL SELECT code+1, CHAR(code+1) FROM Letters WHERE code+1 <= ASCII("Z")) SELECT letter FROM Letters;

Числовая последовательность

DECLARE @startnum INT=1 DECLARE @endnum INT=55 ; WITH gen AS (SELECT @startnum AS num UNION ALL SELECT num+1 FROM gen WHERE num+1<=@endnum) SELECT * FROM gen option (maxrecursion 55)

Подсказка MAXRECURSION может использоваться для предотвращения входа в бесконечный цикл из-за неверно сформированного рекурсивного CTE-выражения.

Объединение временных интервалов

Есть справочник с ценами на продукты, для оптимизации объедением смежные интервалы
DECLARE @ProductPrice TABLE (ProductID int, Price money, BeginDate date, EndDate date NULL) INSERT INTO @ProductPrice VALUES (1, 11.11, "20170101", "20170215") ,(1, 11.11, "20170216", "20170615") ,(1, 22.1, "20170616", null) ,(2, 33, "20170101", "20170201") ,(2, 33, "20170501", "20170601") ,(3, 12, "20170101", "20170215") ,(3, 12, "20170216", null);
Нужно получить в таком виде
--1 11 "20170101" "20170615" --1 22.1 "20170616" null --2 33 "20170101" "20170201" --2 33 "20170501" "20170601" --3 12 "20170101" null
Одно из решений это рекурсия в CTE
;with cte as (select a.ProductID, a.Price, a.BeginDate, a.EndDate from @ProductPrice a left join @ProductPrice b on a.ProductID=b.ProductID and dateadd(day,-1,a.BeginDate)=b.EndDate and a.Price=b.Price where b.BeginDate is null union all select a.ProductID, a.Price, a.BeginDate, b.EndDate from cte a join @ProductPrice b on a.ProductID=b.ProductID and dateadd(day,-1,b.BeginDate)=a.EndDate and a.Price=b.Price) select ProductID, Price, BeginDate, nullif(max(isnull(EndDate,"32121231")),"32121231") EndDate from cte group by ProductID, Price, BeginDate

Объединение однотипных запросов

Вывести номера продавцов с меткой «сильный продавец» или «слабый». Сильным считается продавец со средней стоимостью сделки больше 500, слабым – меньше 500 (запрос приведен на Лист. 39, результат - Табл. 51):

GROUP BY N_Продавца

HAVING avg(Стоимость)<500

GROUP BY N_Продавца

HAVING avg(Стоимость)>500;

Табл. 51. Результат запроса с оператором Union

Вывести номера продавцов с меткой «сильный продавец» или «слабый». Сильным считается продавец со средней стоимостью сделки больше 500, слабым – меньше 500, отсортировать по активности (запрос приведен на Лист. 40, результат - Табл. 52):

SELECT N_Продавца, "Слабый продавец" as Активность FROM Сделки

GROUP BY N_Продавца

HAVING avg(Стоимость)<500

UNION SELECT N_Продавца, "Сильный продавец" as Активность FROM Сделки

GROUP BY N_Продавца

HAVING avg(Стоимость)>500

ORDER BY Активность;

Табл. 52. Результат запроса с Union и Order by

Аналогично работают операторы intersect и except, соответствующие операциям пересечения и разности в реляционной алгебре. Для предметной области «продажи» списки городов покупателей и продавцов могут не совпадать, поэтому мы можем решить разнообразные задачи с этими списками, как показано в Табл. 53.

Табл. 53. Использование операторов соединения однотипных запросов

На Лист. 25 был приведен пример запроса, в котором ищутся подчиненные Иванова. Возникает вопрос, как построить всю иерархию подчиненных, а не только его непосредственных подчиненных. Фактически мы должны применить этот же самый запрос Лист. 25 к результату выполнения его самого, затем еще раз и т.д., пока будут находиться подчиненные на всё более низких уровнях иерархии.

Построить иерархию всех подчиненных Иванова в «в длину» (запрос приведен на Лист. 41, результат - Табл. 54).

Рекурсивные запросы можно опознать по ключевому слову WITH RECURSIVE. Чтобы быть вызванным рекурсивно, запрос фактически должен иметь имя (в данном случае - Прод ). Запрос состоит из двух частей, объединяемых с помощью UNION. В первой части – начальники, во второй части – их подчиненные. Запрос находит первого подчиненного, затем первого подчиненного первого и т.д. Такие запросы называются запросами на поиск «в длину»

Лист. 41. Рекурсивный запрос «в длину»

(SELECT N, Имя

FROM Продавцы

WHERE Имя = ‘Иванов’

SELECT Продавцы. N, Продавцы.Имя

FROM Продавцы, Прод

SELECT * FROM Прод;

Табл. 54. Результат рекурсивного запроса «в длину»

Если нам нужно сперва перечислить всех подчиненных Иванова, затем подчиненных подчиненных Иванова и т.д., то нам нужно использовать рекурсивные запросы «в ширину», используя оператор SEARCH BREADTH FIRST. В запросе с помощью оператора SET устанавливается номер итерации.

Построить иерархию всех подчиненных Иванова «в ширину» (запрос приведен на Лист. 42, результат - Табл. 55).

Лист. 42. Рекурсивный запрос «в ширину»

WITH RECURSIVE Прод (N, Имя, N_Начальника) as

(SELECT N, Имя

FROM Продавцы

WHERE Имя = ‘Иванов’

FROM Продавцы, Прод

WHERE Прод.N = Продавцы.N_Начальника);

SEARCH BREADTH FIRST BY N_Начальника, N

SET order_column

SELECT * FROM Прод

ORDER BY order_column;

Табл. 55. Результат запроса «в ширину»

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

Построить иерархию всех подчиненных Иванова, учесть возможность зацикливания (Лист. 43).

Лист. 43. Рекурсивный запрос с учетом зацикливания

WITH RECURSIVE Прод (N, Имя) as

(SELECT N, Имя

FROM Продавцы

WHERE Имя = ‘Иванов’

SELECT Продавцы. N, Продавцы. Имя

FROM Продавцы, Прод

WHERE Прод.N = Продавцы.N_Начальника);

SET cyrclemark to “Y” default “N”

USING cyrclepath

SELECT * FROM Прод

Д/З 6. Для примера из Д/З 4 придумайте следующие запросы:

1. Запрос по одной таблице, вычисляющий агрегатную функцию с использованием операторов where, having, order by.
2. Запрос соединения нескольких таблиц с использованием оператора where, одна таблица должна использоваться в запросе несколько раз под псевдонимами.
3. Запрос по правому, левому или полному соединению.
4. Запрос с двумя вложенными запросами в конструкциях where и having
5. Запрос с вложенным запросом, используя all, any или exists.
6. Вложенный запрос с объединением двух таблиц (одна из разновидностей join), опосредованно связанных третьей.
7. Объединение однотипных запросов.
8. Рекурсивный запрос.

Вопросы для самопроверки :

1. Чем отличается использование операторов group by, group by rollup, group by rollup cube, grouping, orger by, partition?

2. Чем отличается использование операторов where и having?

3. Какому запросу join … on соответствует оператор where?

4. Какой операции реляционной алгебры соответствует оператор where?

5. Какой операции реляционной алгебры соответствует оператор join?

I"ve copied all the English articles from this blog into the new one. Plus, seems finally I have a lot of new topics to share! I do believe that in the next few months you"ll find something interesting on my new blog. Trust me, I am a developer! :)

Sunday, June 7, 2015

Going further

As you can see from the text above, storing metrics onto the file system is an exceed step - we don"t need them there. Instead we can directly send them into Logstash. This fact leads us to the new architecture:

Here, we can have only one Logstash instance (on the same host as ElasticSearch) listening to UDP socket. In this case we avoid writing data on the local FS and configure our Log4j appender to write directly into Logstash. This approach slightly reminds how SysLog works.

Log4J config: # Root logger option log4j. rootLogger= INFO, logstash # Direct log messages to Logstash log4j. appender. logstash= org. apache. log4j. receivers. net. UDPAppender log4j. appender. logstash. remoteHost= logstash. host log4j. appender. logstash. port= 6666 log4j. appender. logstash. application= YourProject log4j. appender. logstash. encoding= UTF- 8 log4j. appender. logstash. layout= name . krestjaninoff. log . json. LogstashJsonLayout
Logstash config: input { udp { port = > 6666 codec = > json type = > "udp_json" } } ... output { elasticsearch { host = > localhost } }
LogstashJsonLayout code (just a proof of concept): /** * JSON layout for Logstash */ public class LogstashJsonLayout extends Layout { private final Gson gson = new GsonBuilder() . create() ; private final String hostname = getHostname() . toLowerCase() ; private final String username = System . getProperty("user.name" ) . toLowerCase() ; @ Override public String format(LoggingEvent le) { Map< String , Object > message = new LinkedHashMap< > () ; message. put("@timestamp" , le. timeStamp) ; message. put("hostname" , hostname) ; message. put("username" , username) ; message. put("level" , le. getLevel() . toString() ) ; message. put("thread" , le. getThreadName() ) ; if (le. getMessage() instanceof Map) { message. putAll(le. getMessage() ) ; } else { message. put("message" , null ! = le. getMessage() ? le. getMessage() . toString() : null ) ; } return gson. toJson(message) + " \n " ; } private static String getHostname() { String hostname; try { hostname = java. net. InetAddress . getLocalHost() . getHostName() ; } catch (Exception e) { hostname = "Unknown, " + e. getMessage() ; } return hostname; } @ Override public boolean ignoresThrowable() { return false ; } @ Override public void activateOptions() { } }

Sunday, November 23, 2014

Learning

Now imagine that we have a set of pronunciation samples of "odin" word generated by the same person. Using this information we can fit M model parameters to increase the P(O|M) probability for each sample. In other words - we can "teach" the model and improve recognition quality. This "learning" can be done by Baum-Welch algorithm (specification / implementation).

Обучение

Теперь представим, что у нас есть несколько образцов произношения слова "один", сгенерированных конкретным человеком. Подобрав значения модели M так, что бы для всех этих последовательностей звуков модель выдавала максимальную вероятность - обучив модель максимизировав P(O|M), мы сможем значительно улучшить качество распознования. Сделать это можно с помощью алгоритма Баума-Велша (описание / реализация).

Recognition

Theoretically, we already know all that we need to compare (element-wise) our sample (which we"ve read in the previous section) with another one, which text equivalent is known. In other words, we can try to recognize... But we shouldn"t do this:)

Our approach must be stable (at least, a little bit) to any changes in the voice (of a man who uttering the word), volume and speed of pronunciation. Of course, we can"t guarantee that with element-wise comparison of two audio signals.

That"s why we choose the another way.

Frames

First of all let"s split our data into a set of little time intervals – frames. Notice that frames shouldn"t go one by one, instead they should “overlap” each other. Thus the end of the n-frame must intersect with the beginning of n+1-frame.

Frames are more appropriate units for analysis rather than values of singnal"s amplitudes just because we are dealing with waves, and waves are supposed to be analyzed on intervals, not in particular points:) Meanwhile overlapping of frames allows us to smooth analysis results by using a frame as a some kind of “window”, which moves along the original signal (its amplitudes values).

Experiments show us that the optimal frame length should correspond to the interval of 10ms, "overlap" - to 50%. Given that the average word length is 500ms (at least in my experiments) - this length will give us approximately 500 / (10 * 0.5) = 100 frames per word.

Splitting words

The first problem, which must be solved in the process of speech recognition is splitting the speech into different words. Let"s simplify our task and put that the speech contains some pauses (intervals of silence), that can be used as the words splitter.

In this case we need to find the threshold. All values above it will be words, below – silence. Here we can use several ways:

• use a constant (the original signal must be always generated under the same circumstances, in the same way);
• cluster signal"s values into two sets: one with words values and another one with silence (works only if silence takes a big part in the original signal);
• analyze the entropy;

As you can guess, we are going to discuss the last point:) Let"s start from the entropy definition - “a measure of disorder” (c). In our case, the entropy shows how much our signal "varies" within a given frame.

In order to calculate the entropy of a given frame, perform the following steps:

So, we got the value of the entropy. But this is just an another frame"s characteristic. We still need to compare it with something if we want to separate the sound and the silence.
Fortunately, entropy (in contrast to Root Mean Square) is a relatively independent measure. This fact allowed us to put its threashold value as a constant (e.g. 0.1).

Nevertheless, the problems don"t end here:(The entropy may sag in the middle of a word (in vowels) or may suddenly jump (in case of a little noise). In order to fix the first problem we need to use the “minimal distance between two words” and “glue” nearby frame sets, which were divided because of the sag. The second problem can be resolved by using “minimal word length” and removing all the candidates which are not as long as we need (and aren"t used in the first point).

If the speech doesn"t have any pauses between words (or the speaker speaks too fast), we can try to create/extract sets of various subsequences from the original frame set. Then all these subsequences can be used as a source for the recognition process. But that"s absolutely another story:)

MFCC

So, we have the set of frames, which matches with a particular word. We can take the path of least resistance and use average square (root mean square) of all the frame"s elements as theirs numerical characteristic. However, such metric gives us a quite little information for further analysis.

That"s why it"s time to introduce Mel-Frequency Cepstral Coefficients. According to Wikipedia (which, as we know, never lies) MFCC are a kind of signal"s energy representation. Pros of their usage are as follows:

• using of the spectrum of the signal (i.e. expansion by the orthogonal basis of sine functions), which takes into account the “wave” nature of the signal;
• the spectrum is projected onto a special mel-scale , which allows us to extract the most valuable for human perception frequencies;
• amount of calculated coefficients may be limited by any value (e.g. 12), that allows us to “squeeze” the frame and, as a consequence, amount of information to further processing;

It"s time to consider the process of MFCC computing for a particular frame.

Let"s think about our frame as a vector , where N is its size.

Fourier transformation

First of all let"s calculate the spectrum of the signal by computing the discreet Fourier transformation (preferably its “fast” FFT implementation).

It"s also recommended to apply so-called “window” Hamming function to “smooth” values on the frame"s bounds.

As a result we will have the following vector:

It is important to understand that after this conversion, we have X-axis for the frequency (hz) signal, and the Y-axis for the magnitude (as a way to escape from the complex values​​):

Mel-coefficients calculation

Let"s start from the “mel” definition. According to Wikipedia (again), mel is a "psychophysical unit of sound pitch, based on the subjective perception of an average human. It primarily depends on the frequency of the sound (as well as on volume and tone). In other words, this value shows us how much the sound of a certain frequency is "valuable" for us.

Frequency can be converted into mel-values by the following formula (remind it as "formula-1"):

Backward transformation looks in the following way (remind it as "formula-2"):

Graph of mel/frequency scale:

But let"s get back to our task. Assume that we have a frame which size is N = 256 elements. We know (from the audio format data) that the frequency of the frame is 16000hz. Let"s put that the human speech belongs to the range hz. Amount of mel-coefficients that we want to find is M = 10.

In order to expand the spectrum (which we"ve calculated above) by the mel-scale, we need to create the “comb” of mel-filters. In fact, each mel-filter is a triangular window function , which summarizes amount of energy at the certain frequency range (thus calculates the mel-coefficient). Hence, since we know the amount of mel-coefficients and the frequency range, we can construct the following set of filters:

Notice, the greater the index number of the mel-coefficient is, the wider the base of the filter is. This is because the process of splitting frequency bands into the filters intervals happens on the mel-scale (not on the frequency-scale).

But I digress. For our case the frequency range is . According to the “formula-1” on the mel-scale this interval transforms into .

Next, we need 12 reference points to build 10 triangular filters:

Notice, on the mel-scale the points are located uniformly. Let"s transform the values back to frequency using the “formula-2”:

As you can see, our values start to stretch, thus aligning the growth dynamics of the "significance" of the sound on the low and high frequencies.

Now let"s impose the scale (which we got above) on the spectrum of our frame. As we remember, X-axis is for frequency. Length of the spectrum is 256 elements, which refers to 16000Hz diapason. Solving the simple proportion we obtain the following formula:

in our case this is equivalent to

That is all! Since we know the reference points on the X-axis of our spectrum we can easily construct the necessary filters by the following formula:

Applying the mel-filters

Applying the filter to the spectrum mean pairwise multiplying the filter values ​​with the spectrum values. The sum of the elements in the result vector is a mel-coefficient. Since we have M-filters, the number of mel-coefficients will be the same.

However, we need to apply mel-filters not to the spectrum, but to its energy. Then we must logarithm the result. It"s believed that the trick above decreases the sensitivity to noise ratios.

Cosine transformation

Discrete Cosine Transform (DCT) is used in order to get the "cepstral" coefficients. It allows to “squeeze” the results, increasing the importance of the first coefficients and reducing the importance of the last ones.

In current case we use DCT-II without additional multiplication on the scale factor .

Now we have the set of M mfcc-coefficients for each frame. These coefficients can (and will) be used for the further analysis!

Recognition algorithm

Here, dear reader, you"ll face the major disappointment. In the internets I"ve seen a lot of highly (and not very) intelligent debates about what is the best way for speech recognizing. Somebody stands up for Hidden Markov Models, someone - for neural networks... someone"s thoughts can"t be understood at all:)

The only thing that we need to do with that algorithm is changing of the distance calculation logic. We must remember that the mfcc-vector of the model is a sequence of mfcc-subvectors (M-size) obtained from the frames. So, DTW algorithm must calculate distances between these subvectors, not their elements. Hence, elements of distance matrix are Euclid distances between frame based mfcc-subvectors.

Experiments

I haven"t been able to verify the approach on a big amount of “training” samples. As for test results based on 3 samples education... They are quite bad – only 65% correct recognitions.

However, my task was implementation of the simplest speech recognition application. So called “proof of concept” :)

Implementation

The attentive reader has noticed that the article contains a lot of references on the GitHub project. It"s worth to say that it"s my first C++ project since the university times. Also it"s my first attempt to calculate something more complicated than the arithmetic mean since the same times... In other words “it comes with absolutely no warranty” (с) :)

Пролог

Начнём с того, что наша речь - это последовательность звуков. Звук в свою очередь - это суперпозиция (наложение) звуковых колебаний (волн) различных частот. Волна же, как нам известно из физики, характеризуются двумя атрибутами - амплитудой и частотой.

Таким вот образом механические колебания превращаются в набор чисел, пригодный для обработки на современных ЭВМ.

Отсюда следует, что задача распознавания речи сводится к "сопоставлению" множества численных значений (цифрового сигнала) и слов из некоторого словаря (русского языка, например).

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

Входные данные

Допустим у нас есть некоторый файл/поток с аудиоданными. Прежде всего нам нужно понять, как он устроен и как его прочесть. Давайте рассмотрим самый простой вариант - WAV файл.

Формат подразумевает наличие в файле двух блоков. Первый блок - это заголовка с информацией об аудиопотоке: битрейте, частоте, количестве каналов, длине файла и т.д. Второй блок состоит из "сырых" данных - того самого цифрового сигнала, набора значений амплитуд.

Логика чтения данных в этом случае довольно проста. Считываем заголовок, проверяем некоторые ограничения (отсутствие сжатия, например), сохраняем данные в специально выделенный массив.

Распознавание

Чисто теоретически, теперь мы можем сравнить (поэлементно) имеющийся у нас образец с каким-нибудь другим, текст которого нам уже известен. То есть попробовать "распознать" речь... Но лучше этого не делать:)

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

Поэтому мы пойдем несколько иным путём.

Фреймы

Первым делом разобьём наши данные по небольшим временным промежуткам - фреймам. Причём фреймы должны идти не строго друг за другом, а “внахлёст”. Т.е. конец одного фрейма должен пересекаться с началом другого.

Фреймы являются более подходящей единицей анализа данных, чем конкретные значения сигнала, так как анализировать волны намного удобней на некотором промежутке, чем в конкретных точках. Расположение же фреймов “внахлёст” позволяет сгладить результаты анализа фреймов, превращая идею фреймов в некоторое “окно”, движущееся вдоль исходной функции (значений сигнала).

Опытным путём установлено, что оптимальная длина фрейма должна соответствовать промежутку в 10мс, "нахлёст" - 50%. С учётом того, что средняя длина слова (по крайней мере в моих экспериментах) составляет 500мс - такой шаг даст нам примерно 500 / (10 * 0.5) = 100 фреймов на слово.

Разбиение слов

Первой задачей, которую приходится решать при распознавании речи, является разбиение этой самой речи на отдельные слова. Для простоты предположим, что в нашем случае речь содержит в себе некоторые паузы (промежутки тишины), которые можно считать “разделителями” слов.

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

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

Как вы уже догадались, речь сейчас пойдёт о последнем пункте:) Начнём с того, что энтропия - это мера беспорядка, “мера неопределённости какого-либо опыта” (с). В нашем случае энтропия означает то, как сильно “колеблется” наш сигнал в рамках заданного фрейма.

И так, мы получили значение энтропии. Но это всего лишь ещё одна характеристика фрейма, и для того, что бы отделить звук от тишины, нам по прежнему нужно её с чем-то сравнивать. В некоторых статьях рекомендуют брать порог энтропии равным среднему между её максимальным и минимальным значениями (среди всех фреймов). Однако, в моём случае такой подход не дал сколь либо хороших результатов.
К счастью, энтропия (в отличие от того же среднего квадрата значений) - величина относительно самостоятельная. Что позволило мне подобрать значение её порога в виде константы (0.1).

Тем не менее проблемы на этом не заканчиваются:(Энтропия может проседать по середине слова (на гласных), а может внезапно вскакивать из-за небольшого шума. Для того, что бы бороться с первой проблемой, приходится вводить понятие “минимально расстояния между словами” и “склеивать” близ лежачие наборы фреймов, разделённые из-за проседания. Вторая проблема решается использованием “минимальной длины слова” и отсечением всех кандидатов, не прошедших отбор (и не использованных в первом пункте).

Если же речь в принципе не является “членораздельной”, можно попробовать разбить исходный набор фреймов на определённым образом подготовленные подпоследовательности, каждая из которых будет подвергнута процедуре распознавания. Но это уже совсем другая история:)

MFCC

И так, мы у нас есть набор фреймов, соответствующих определённому слову. Мы можем пойти по пути наименьшего сопротивления и в качестве численной характеристики фрейма использовать средний квадрат всех его значений (Root Mean Square). Однако, такая метрика несёт в себе крайне мало пригодной для дальнейшего анализа информации.

Вот тут в игру и вступают Мел-частотные кепстральные коэффициенты (Mel-frequency cepstral coefficients). Согласно Википедии (которая, как известно, не врёт) MFCC - это своеобразное представление энергии спектра сигнала. Плюсы его использования заключаются в следующем:

• Используется спектр сигнала (то есть разложение по базису ортогональных [ко]синусоидальных функций), что позволяет учитывать волновую “природу” сигнала при дальнейшем анализе;
• Спектр проецируется на специальную mel-шкалу , позволяя выделить наиболее значимые для восприятия человеком частоты;
• Количество вычисляемых коэффициентов может быть ограничено любым значением (например, 12), что позволяет “сжать” фрейм и, как следствие, количество обрабатываемой информации;

Давайте рассмотрим процесс вычисления MFCC коэффициентов для некоторого фрейма.

Представим наш фрейм в виде вектора , где N - размер фрейма.

Разложение в ряд Фурье

Первым делом рассчитываем спектр сигнала с помощью дискретного преобразования Фурье (желательно его “быстрой” FFT реализацией).

То есть результатом будет вектор следующего вида:

Важно понимать, что после этого преобразования по оси Х мы имеем частоту (hz) сигнала, а по оси Y - магнитуду (как способ уйти от комплексных значений):

Расчёт mel-фильтров

Начнём с того, что такое mel. Опять же согласно Википедии, mel - это “психофизическая единица высоты звука”, основанная на субъективном восприятии среднестатистическими людьми. Зависит в первую очередь от частоты звука (а так же от громкости и тембра). Другими словами, эта величина, показывающая, на сколько звук определённой частоты “значим” для нас.

Преобразовать частоту в мел можно по следующей формуле (запомним её как "формула-1"):

Обратное преобразование выглядит так (запомним её как "формула-2"):

График зависимости mel / частота:

Но вернёмся к нашей задаче. Допустим у нас есть фрейм размером 256 элементов. Мы знаем (из данных об аудиоформате), что частота звука в данной фрейме 16000hz. Предположим, что человеческая речь лежит в диапазоне от hz. Количество искомых мел-коэффициентов положим M = 10 (рекомендуемое значение).

Для того, что бы разложить полученный выше спектр по mel-шкале, нам потребуется создать “гребёнку” фильтров. По сути, каждый mel-фильтр это треугольная оконная функция , которая позволяет просуммировать количество энергии на определённом диапазоне частот и тем самым получить mel-коэффициент. Зная количество мел-коэффициентов и анализируемый диапазон частот мы можем построить набор таких вот фильтров:

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

Но мы опять отвлеклись. И так для нашего случая диапазон интересующих нас частот равен . Согласно формуле-1 в на мел-шкале этот диапазон превращается в .

m[i] =

Обратите внимание, что на мел-шкале точки расположены равномерно. Переведём шкалу обратно в герцы с помощью формулы-2:

h[i] =

Как видите теперь шкала стала постепенно растягиваться, выравнивая тем самым динамику роста “значимости” на низких и высоких частотах.

Теперь нам нужно наложить полученную шкалу на спектр нашего фрейма. Как мы помним, по оси Х у нас находится частота. Длина спектра 256 - элементов, при этом в него умещается 16000hz. Решив нехитрую пропорцию можно получить следующую формулу:

f(i) = floor((frameSize+1) * h(i) / sampleRate)

что в нашем случае эквивалентно

f(i) = 4, 8, 12, 17, 23, 31, 40, 52, 66, 82, 103, 128

Вот и всё! Зная опорные точки на оси Х нашего спектра, легко построить необходимые нам фильтры по следующей формуле:

Применение фильтров, логарифмирование энергии спектра

Применение фильтра заключается в попарном перемножении его значений со значениями спектра. Результатом этой операции является mel-коэффициент. Поскольку фильтров у нас M, коэффициентов будет столько же.

Однако, нам нужно применить mel-фильтры не к значениям спектра, а к его энергии. После чего прологарифмировать полученные результаты. Считается, что таким образом понижается чувствительность коэффициентов к шумам.

Косинусное преобразование

Дискретное косинусное преобразование (DCT) используется для того, что бы получить те самые “кепстральные” коэффициенты. Смысл его в том, что бы “сжать” полученные результаты, повысив значимость первых коэффициентов и уменьшив значимость последних.

В данном случае используется DCTII без каких-либо домножений на (scale factor).

Теперь для каждого фрейма мы имеем набор из M mfcc-коэффициентов, которые могут быть использованы для дальнейшего анализа.

Примеры код для вышележащих методов можно найти .

Алгоритм распознавания

Вот тут, дорогой читатель, тебя и ждёт главное разочарование. В интернетах мне довелось увидеть множество высокоинтеллектуальных (и не очень) споров о том, какой же способ распознавания лучше. Кто-то ратует за Скрытые Марковские Модели, кто-то - за нейронные сети, чьи-то мысли в принципе невозможно понять:)

В любом случае немало предпочтений отдаётся именно СММ , и именно их реализацию я собираюсь добавить в свой код… в будущем:)

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

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

Теперь возьмем в руки айфон/андроид и пройдёмся по L коллегам с просьбой продиктовать эти слова под запись. Далее поставим в соответствие (в какой-нибудь локальной БД или простом файле) каждому слову L наборов mfcc-коэффициентов соответствующих записей.

Это соответствие мы назовём “Модель”, а сам процесс - Machine Learning! На самом деле простое добавление новых образцов в базу имеет крайне слабую связь с машинным обучением… Но уж больно термин модный:)

Теперь наша задача сводится к подбору наиболее “близкой” модели для некоторого набора mfcc-коэффициентов (распознаваемого слова). На первый взгляд задачу можно решить довольно просто:

• для каждой модели находим среднее (евклидово) расстояние между идентифицируемым mfcc-вектором и векторами модели;
• выбираем в качестве верной ту модель, среднее расстояние до которой будет наименьшим;

Однако, одно и тоже слово может произносится как Андреем Малаховым, так и каким-нибудь его эстонским коллегой. Другими словами размер mfcc-вектора для одного и того же слова может быть разный.

К счастью, задача сравнения последовательностей разной длины уже решена в виде Dynamic Time Warping алгоритма. Этот алгоритм динамическо программирования прекрасно расписан как в буржуйской Wiki , так и на православном Хабре .

Единственное изменение, которое в него стоит внести - это способ нахождения дистанции. Мы должны помнить, что mfcc-вектор модели - на самом деле последовательность mfcc-“подвекторов” размерности M, полученных из фреймов. Так вот, DTW алгоритм должен находить дистанцию между последовательностями эти самых “подвекторов” размерности M. То есть в качестве значений матрицы расстояний должны использовать расстояния (евклидовы) между mfcc-“подвекторами” фреймов.

Эксперименты

У меня не было возможности проверить работу данного подхода на большой “обучающей” выборке. Результаты же тестов на выборке из 3х экземпляров для каждого слова в несинтетических условиях показали мягко говоря нелучший результат - 65% верных распознаваний.

Тем не менее моей задачей было создание максимального простого приложения для распознавания речи. Так сказать “proof of concept” :)

Реализация

Внимательный читатель заметил, что статья содержит множество ссылок на GitHub-проект. Тут стоит отметить, что это мой первый проект на С++ со времён университета. Так же это моя первая попытка рассчитать что-то сложнее среднего арифметического со времён того же университета... Другими словами it comes with absolutely no warranty (с) :)