Una codificación prefija para un idioma artificial

ESCUELA T´ ECNICA SUPERIOR DE INGENIER´ IA INFORM´ ATICA GRADO EN INGENIER´ IA INFORM´ ATICA UNA CODIFICACI´ ON PREFIJA PARA UN IDIOMA ARTIFICIAL A PREFIX ENCODING FOR A CONSTRUCTED LANGUAGE Realizado por Jos´e Antonio Ortega Toro Tutorizado por Francisco Jos´e Vico Vela Departamento Lenguajes y Ciencias de la Computaci´on UNIVERSIDAD DE M´ ALAGA M´ ALAGA, SEPTIEMBRE DE 2015 Fecha defensa: El Secretario del Tribunal Resumen: Este trabajo se centra en el estudio formal y t´ecnico de algunos componentes de un lenguaje artificial. Como primera parte del trabajo, se estudiar´a una posible codificaci´on para el lenguaje, haciendo ´enfasis en que se trate de una codificaci´on libre de prefijo, para lo cu´al se realizar´a una extensi´on del algoritmo de Huffman de binario a n-ario. Debido a que en el lenguaje no podemos conocer a priori la frecuencia de uso de las palabras, se har´a un estudio y se propondr´an diversas estrategias para un sistema de palabras abierto, analizando previamente el n´umero de palabras existentes en lenguajes naturales actuales. Como posible mejora a la codificaci´on, tambi´en analizaremos el problema de la p´erdida de sincronizaci´on, as´ı como su soluci´on: la auto sincronizaci´on (self-synchronizing codes), un estudio de los t-codes con el n´umero de palabras posibles para el lenguaje, as´ı como otras alternativas. Por ´ultimo, y desde un apartado menos formal y m´as t´ecnico, se han desarrollado diversas aplicaciones para la implementaci´on del lenguaje: un sintetizador de voz, un reconocedor de voz y una fuente para el uso del lenguaje en procesadores de texto. Para cada uno de estos desarrollos se detallar´a el proceso seguido para su construcci´on, as´ı como los problemas encontrados o por resolver en cada uno de ellos. Palabras claves: teor´ıa de la codificaci´on, lenguaje artificial, teor´ıa de la informaci´on, c´odigos libres de prefijo, codificaci´on de Huffman, reconocimiento de voz, s´ıntesis de voz. Abstract: This work focuses in the formal and technical analysis of some aspects of a constructed language. As a first part of the work, a possible coding for the language will be studied, emphasizing the prefix coding, for which an extension of the Huffman algorithm from binary to n-ary will be implemented. Because of that in the language we can’t know a priori the frequency of use of the words, a study will be done and several strategies will be proposed for an open words system, analyzing previously the existing number of words in current natural languages. As a possible upgrade of the coding, we’ll take also a look to the synchronization loss problem, as well as to its solution: the self-synchronization, a t-codes study with the number of possible words for the language, as well as other alternatives. Finally, and from a less formal approach, several applications for the language have been developed: A voice synthesizer, a speech recognition system and a system font for the use of the language in text processors. For each of these applications, the process used for its construction, as well as the problems encountered and still to solve in each will be detailed. Keywords: coding theory, constructed language, information theory, prefix code, huffman coding, speech recognition, voice synthesization. Contents List of Figures 7 List of Tables 9 List of Listings 11 1 Introduction 13 2 Unilan 17 2.1 Introduction ................................... 17 2.2 Problems solved by Unilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Alphabet..................................... 18 2.4 Vocabulary.................................... 19 2.5 Phonetics..................................... 19 3 Theoretical study 21 3.1 Introduction ................................... 21 3.2 PrefixCoding .................................. 23 3.2.1 Algorithms................................ 24 3.2.2 ExtendingHuffman ........................... 28 3.2.3 Numberofwords............................. 29 3.3 Self-Synchronization............................... 33 3.3.1 Introduction ............................... 33 3.3.2 T-Codes ................................. 34 3.3.3 Suffixapproach ............................. 35 4 Applications 37 4.1 TexttoSpeech(TTS).............................. 37 4.1.1 Introduction ............................... 37 4.1.2 Current TTS engines . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.1.3 Implementation ............................. 40 4.1.4 Results.................................. 43 4.2 SpeechtoText(STT).............................. 44 4.2.1 Introduction ............................... 44 4.2.2 Techniques and engines . . . . . . . . . . . . . . . . . . . . . . . . . 45 5 Contents 4.2.3 Implementation ............................. 47 4.2.4 Results.................................. 48 4.3 SystemFont ................................... 50 5 Discussion & Conclusions 53 Bibliography 57 Annexes A Speech-to-text (STT) Implementation 1 B SVG file generation scripts 9 6 List of Figures 2.1 Unilan symbols example (CA - LO - RU) . . . . . . . . . . . . . . . . . . . . 19 3.1 Binary tree representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 ASCIITable ................................... 22 3.3 Shannon-Fano example: Code representation . . . . . . . . . . . . . . . . . . 25 3.4 Huffman example: Code representation . . . . . . . . . . . . . . . . . . . . . 28 3.5 Tree representation (ETE toolkit) . . . . . . . . . . . . . . . . . . . . . . . . 28 4.1 Wheatstone’s reconstruction of von Kempelen’s speaking machine. . . . . . . 38 4.2 The VODER speech synthesizer. . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.3 Some milestones in speech analysis. . . . . . . . . . . . . . . . . . . . . . . . 39 4.4 Phoneme errors vs Interphoneme separation . . . . . . . . . . . . . . . . . . . 49 4.5 Random word errors vs Interphoneme separation . . . . . . . . . . . . . . . . 49 4.6 Building the Unilan’s font in FontForge . . . . . . . . . . . . . . . . . . . . . 50 4.7 Unilan’s font in text editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 7 List of Tables 2.1 Unilan’s alphabet binary representation . . . . . . . . . . . . . . . . . . . . . 19 3.1 Shannon-Fanoexample ............................. 25 3.2 Huffmanexample ................................ 28 3.3 Number of different words for differents languages . . . . . . . . . . . . . . . 29 3.4 T-Codeexample ................................. 35 4.1 Word success rate results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2 Phoneme breakdown success rate results . . . . . . . . . . . . . . . . . . . . 44 9 Chapter 2 Unilan 2.1 Introduction Unilan is a pidgin artificial language that intends to become a natural language by the interaction of humans with machines. Different from a creole language, Unilan does not inherit its vocabulary from any phylogenetic parent language (it is, an a priori language), instead, it will be created by an algorithm as new words are defined within Unilan’s semantics. Since a pidgin language is a fundamentally simple form of communication, the grammar and phonology are usually as simple as possible, and they consist of: •Uncomplicated clausal structure (e.g., no subordinate clauses, etc.) •Reduction or elimination of syllable codas •Reduction of consonant clusters or breaking them with epenthesis •Basic vowels, such as [a, e, i, o, u] •No tones, such as those found in West African and Asian languages •Use of separate words to indicate tense, usually preceding the verb •Use of reduplication to represent plurals, superlatives, and other parts of speech that represent the concept being increased •A lack of morphophonemic variation 17 Chapter 2. Unilan 2.2 Problems solved by Unilan •1 glyph →1 letter –Allography: There is no distinction between uppercase and lowercase (or other glyphs). •1 glyph →1 digit –Phonetics of numbers. •1 morpheme →1 phoneme –There is no morphophonemic variation, each symbol represents a different syllable, and there are no allophones (as proposed in the Shavian alphabet). •1 word →1 concept –Homonymy: A word cannot have multiple unrelated meanings. –Polysemy: A word cannot have multiple related meanings. •Computer language = natural language •Semantic network –Resolving the semantics ambiguities. •Centralized words generator –This avoids the phonetic, syntactic and semantic drift. •Sign language, since every symbol can be represented with the two hands (one for the consonant, the other for the vowel), sentences shortens with respect to human languages, and there are no interruptions in the communication. 2.3 Alphabet Each letter is an open syllable with one, and only one onset consonant, and it results from a typographic ligature of a consonant and a vowel (always in this order) of a subset of the latin alphabet. 16 consonants and the 5 vowels are used, yielding an 80-character set. Alphabetical order is determined, firstly, by the order of occurrence of the consonant in the latin alphabet, and, secondly, by the order of the vowels (ba, be, bi, bo, bu, ca, . . . , zu). Here is the latest version of the letters used and its binary representation: 18 Chapter 2. Unilan Table 2.1: Unilan’s alphabet binary representation AEIOUBCDFGJLMNPRSTWYZ OO OO OO OO O OOO OOO OOO OOO OOO OOO O OOO O O OOO OOO OOO OOO O O O O OOO O O O O O O O O O O O O O O O O O O O O O O O O O O O O OO O O OOO O O O OOO O O O O O O O OOO OOO OOO OOO O O O OOO OOO O O O O O O O O O O O O O O O O O O O O O O O O O O O O OO OO OO OO OOO OOO OOO O OOO OOO OOO O O O O O O O OOO O OOO O OOO And these are some examples of symbols in this alphabet. Figure 2.1: Unilan symbols example (CA - LO - RU) 2.4 Vocabulary Words are strings of symbols, selected according to its expected frequency of use, and to its semantics (so as to avoid conflicts with words meaning too similar or too opposed meanings). Each word represents a single concept. There are no variations of a word, no prefixes or suffixes, but since words come on a row, it can be seen as a way of suffixing (adjectives follow nouns, like in Spanish), if read as a single word. In a way, it’s like compound words (e.g. ‘moonlight’). 2.5 Phonetics Unilan has a phonemic alphabet, that is, each symbol corresponds to a phoneme. The pronunciation is based on the Latin IPA, and sounds similar to the Spanish one, with small differences: •‘ce’ and ‘ci’ are pronounced like /ke/ and /ki/. •‘ra’, ‘re’, . . . ‘ru’ are always pronounced like /ra/, /re/, . . . , /ru/. •‘ge’ and ‘gi’ are pronounced like /ge/ and /gi/. 19 Chapter 3 Theoretical study 3.1 Introduction After we’ve introduced Unilan, let’s move onto the coding part, and let’s start talking about what a code is. Let Σ = {a1, ..., an}be an alphabet; we call the aivalues symbols. A block code Cof length nover Σis a subset of Σn. A vector c∈Cis called a codeword. The number of elements in C, denoted |C|, is called the size of the code. A code of length nand size Mis called an (n, M)-code. We can represent a code easily in a tree structure. The representation can be done for any size b. The root of the tree is tagged with the empty word, and the nodes are tagged recursively. The children of the node tagged with (w) will be tagged like w0and w1(when b= 2). 0 00 01 1 10 11 Figure 3.1: Binary tree representation 21 Chapter 3. Theoretical Study Examples of codes applications are everywhere: Morse, ASCII, QR codes, train tickets... Figure 3.2: ASCII Table Codes can be divided into two groups, fixed-length codes and variable-length codes. For example, the ASCII is an example of fixed-length code, because every symbol is coded with the same number of bits. And what is the advantage of using variable-length codes? Let’s think on a book, if there are some letters that appear more frequently, it would be nice if these letters were encoded with a shorter codeword, resulting in a short message, that is, more efficient. Something like that occurs in a language. Ideally, the more used a word is, the shorter it is. Maybe in the case of Unilan we don’t know a priori the expected frequency for each word, but it also would be strange to have a language with all the words with the same length, wouldn’t it? The variable-length codes lead us to the the following topic, called the decoding problem: The symbols appear in a determined order in a message, so we can say that a message is a part of a flow with an established order by a process that happens in real-time. ξ1ξ2ξ3... 22 Chapter 3. Theoretical Study Each ξkis a variable that can take every symbol of the alphabet Sas value, and its actual value is the symbol that occurs at instant k(k= 1,2,3, ...). We have a decoding function c:S→T∗that replaces the symbols in the alphabet Swith a coded string from the alphabet T. Let’s consider the alphabet S=w, x, y, z and c:S→B∗as: w→10, x →01, y →11, z →011. If we receive the string 10011011 we can see that it can represent two different strings: wxwy →10011011 wzz →10011011 This would be a problem, so it would be reasonable as a requirement that C is a uniquely decodable code, that is, each coded string correspond to a unique original string. Also we would like that the string is decoded in sequential order, without having to wait to the end of the message. With a prefix coding, we’ll ensure that our code is a uniquely decodable code, so next we’ll give a definition of what a prefix code is, and what are the techniques for get it. 3.2 Prefix Coding We’ll say that the codeword qis a prefix of another codeword q0if the unique path from q0to the tree root goes through q. A code Cwill be prefix-free if for all codeword q, any descendant node of qisn’t a codeword. This is, we can ignore all the nodes that are descendant of q. If we ignore all the nodes that aren’t codewords nor codeword prefixes, we’ll have a finite binary tree, and the codewords of Cwill be its leafs. Formally: A prefix code / prefix-free code / instantaneous code / context-free code is a type of code system (typically a variable-length code) distinguished by its possession of the “prefix property”: there is no code word that is a prefix of any other codeword. Given the code L={a1...an}, ai∈Σ+it will be a prefix code (noted P(L)), if ∀β∈ Σ+, i, j |aiβ6=aj. Theorem: If a code c:S→T∗is prefix-free, then it is uniquely decodable. On the next part we’ll focus on some of the algorithms for creating prefix-free codes. 23 Chapter 3. Theoretical Study 3.2.1 Algorithms First, we’ll start with the technique introduced by Claude Shannon and Robert Fano[3], the Shannon-Fano coding. The code is constructed as follows: •Shannon-Fano algorithm 1. Given a list of symbols, create its probability list or appearing frequency, given as result the relative frequency for each symbol. 2. Then, sort the symbol lists according to the frequency in descendent order. 3. After that, the list is divided so that the total frequency of each part are as nearly as possible. 4. The first part of the list will be assigned the digit ‘0’, and ‘1’ to the second part. That means that the codeword for the symbols in the first part of the list will begin with ‘0’, and the same with ‘1’ for the symbols in the second part of the list. 5. To finish, apply steps 3 and 4 again to the two sublists, until each sublist corresponds to a symbol. Here is a implementation of the algorithm in python: def shannon ( symbols , count ): # Step 1 total = float(sum( count )) relative_frequencies = [] for freq in count : relative_frequencies . append ( freq / total ) # Step 2 symbols = sorted ( symbols , key= lambda a: relative_frequencies [ symbols . index (a)] , reverse = True ) relative_frequencies . sort ( reverse = True ) codewords = [’’] * len ( symbols ) shannon_aux ( symbols , relative_frequencies , codewords , 0 , len ( symbols ) - 1) return zip (symbols , codewords ) def shannon_aux ( symbols , relative_frequencies , codewords , start , end ): if start != end: # Step 3 ind_split = 1 left = relative_frequencies [ start ] right = sum ( relative_frequencies [ start +1: end +1]) 24 Chapter 3. Theoretical Study while ind_split != end: next_left = left + relative_frequencies [ start + ind_split ] next_right = right - relative_frequencies [ start + ind_split ] if abs ( next_left - next_right ) < abs ( left - right ): left = next_left right = next_right ind_split += 1 else: break # Step 4 for i in range ( start , start + ind_split ): codewords [i] += ’0’ for i in range ( start + ind_split , end + 1): codewords [i] += ’1’ # Step 5 shannon_aux ( symbols , relative_frequencies , codewords , start , start + ind_split - 1) shannon_aux ( symbols , relative_frequencies , codewords , start + ind_split , end) Listing 3.1: Python implementation of the Shannon-Fano algorithm And here is the output for next symbol distribution example: Table 3.1: Shannon-Fano example Symbol Frecuency Codeword A 24 00 B 12 01 C 10 10 D 8 110 E 8 111 A B C D E Figure 3.3: Shannon-Fano example: Code representation The previous example results in a code with an average length of 2.26 bits per symbol. However, the Shannon-Fano coding does not always produce the optimal code, and for this reason is 25 Chapter 3. Theoretical Study and this results in multiplying all the terms by sin this form ni=s(ni−1−xi−1) Implementation: this script in python will compute the maximum number of words for each length, depending on the scheme of distribution of words. def count (s, x ): # Maximum number of words of a given length for an alphabet and a list of words # s : cardinality of the alphabet , number of symbols ( positive integer ) # x : number of words of given lengths (list of positive integers ) # # computes vector n where # n_k = s(n_k -1 - x_k -1) # with n_1 = s # m is the list of maximum values # x is the list of words reserved # # example # x = count (80 , [12 , 1000 , 100000]) # # returns list of length 4, so the next length is computed . m = [s] n = [s] for l in range (1, len (x) + 1): m. append (s * m [l -1]) n. append (s * ( n[l -1] - x[l -1])) x. append (n[ -1]) return x Listing 3.3: Python implementation of the number of words algorithm The final coding will be chosen taking into account different aspects of the language, such as the morphology or semantics. 32 Chapter 3. Theoretical Study 3.3 Self-Synchronization 3.3.1 Introduction As future work, we have to look beyond in the use of the language. Even in a scenario of perfect communication (without noise), we all know that no one knows every word from a language (partial knowledge), this implies a problem using the prefix coding because the listener could not know part of the code tree structure that needs to decode the communication flow (does not know a word, for example), so in that moment occurs what is called a synchronization loss, the listener doesn’t know where the current word ends and where the next begins. The codes that allow to recover from this situations are called self-synchronizing codes, although there are several types of self-synchronizing codes. To speak more precisely about the self-synchronizing properties, we will make some definitions, which can be found in the work of Gilbert and Moore[5]. Given any encoding Cand any 1. finite sequences xand ysuch that xis not the enciphered form (with respect to encoding C) of any message, and xy is a presumed message if zis a finite sequence of binary digits such that both xyz and yz are complete enciphered messages, we will say that zis a synchronizing sequence for xand y. Given any uniquely decipherable encoding C, which has some codes of length more than 1, exactly one of the three statements given below will hold: •For all xand y, there is no zsuch that zis a synchronizing sequence for xand y. The encoding Cwill then be said to be never-self-synchronizing. •For each xand y, there is a zwhich is a synchronizing sequence for xand y. The encoding Cwill then be said to be completely self-synchronizing. •For some xand ythere is a synchronizing sequence, but for other uand vthere is no synchronizing sequence. The encoding Cwill then be said to be partially selfsynchronizing. Furthermore, we will define a sequence zto be a universal synchronizing sequence for the encoding Cif zis the same synchronizing sequence for all xand y. Theorem: Given an exhaustive encoding C, then Cis completely self-synchronizing if and only if there exists a zwhich is a universal synchronizing sequence for C. 33 Chapter 3. Theoretical Study Now let’s consider self-synchronization in Huffman codes[6]: Let Cbe a Huffman code. We say Cis synchronous if there is a codeword c=c1c2...cnin C satisfying the following two conditions: 1. For all x=x1x2...xmin Csuch that m > n and cis a substring of x, we have c1c2...cn=xm−n+1...xmbut c1c2...cn6=xixi+1...xi+n−1for any i6=m−n+ 1 2. For any j < n such that c1c2...cjcan be written as a suffix, the sequence cj+1cj+2...cn is a string of codewords. If such a codeword cexists it is called a synchronizing codeword for C. This definition is justified by observing that conditions 1. and 2. guarantee that whenever cis received (without errors), the decoder must automatically resynchronize, regardless of the preceding synchronization slippage. So, finding a code with a universal synchronizing sequence will be prefered for synchronization loss problems, and the shorter and the more frequent the sequence is, the better. 3.3.2 T-Codes The original T-Codes were published in 1984 by Titchener[7][8]. This work gave an algorithm for generating families of codes that were self-synchronizing by nature. This type of codes are statistically self-synchronizing, that in best cases can synchronize with about 1.5 codewords of delay. The T-Code construction algorithm is simple. Code sets are constructed by augmenting lower level T-Code code sets, with the lowest level being the code set 0 and 1 (binary scenario). The augmentation process consists of writing out a list with two copies of the lower level code set, and then sacrificing a codeword from the first half of the list and using it as a prefix for every codeword in the second half of the list. This produces a new code set which has nearly twice the number of codewords of the lower level code set. An example of this process is given on the next table. 34 Chapter 3. Theoretical Study Table 3.4: T-Code example Level 0 Level 1 Level 2 Prefix 0 Prefix 01 0 1 →- 1 00 01 - 1 00 →- - 011 0100 0101 Because in each iteration of the algorithm the longest codeword increases in at least one symbol, it is not useful for Unilan (at least we want a core language with not so much vocabulary). 3.3.3 Suffix approach Self-synchronization with suffixes A idea for making our always-self-synchronizing language, we can think on using suffixes as universal synchronizing sequences. If our alphabet consists of n symbols and we take a set of symbols Sas suffix (s=|S|) forcing the language words to end always on some of these symbols (xy ∈C, x ∈Σ∗, y ∈S), then Cwill be completely self-synchronizing, that is, if there is a loss of synchronization only we’ll have to wait to the current word’s end and reach the suffix to recover the synchronization. This can be seen in the coding tree as follows: Only the symbols from Sare leaf nodes, and all the symbols that are in Σ−Swill be always internal nodes. The number of words that we’ll have using this technique will be (using ssymbols from Σas suffixes): •swords of length 1 •(n−s)·swords of length 2 •(n−s)2·swords of length 3 •... •(n−s)l·swords of length l 35 Chapter 3. Theoretical Study For example, for n= 80 and s= 20: •20 words of length 1 •1.200 words of length 2 •72.000 words of length 3 •4.320.000 words of length 4 •... Self-synchronization using spaces Another more natural idea is the use of delimiters (spaces) instead of suffixes. This would result in some advantages: •A larger word count that with suffixes (same numbers as seen in prefix code section) •Better legibility On the other hand, the information flow would be more inefficient (information’s overhead). 36 Chapter 4 Applications As a way for putting in practice the future language coding, three applications have been developed, a text-to-speech engine (TTS), a first try of a speech recognition system (STT) and a system font for Unilan. 4.1 Text to Speech (TTS) 4.1.1 Introduction The first ‘human speech machines’ date back one thousand years, with the “Brazen Head”, a legendary automaton that was supposed to be able to answer any question. But we can say that attempts to synthesize voice have been done since two hundred years ago. For example, in 1791, Wolfgang von Kempelen introduced his “Acoustic-Mechanical Speech Machine”, and in about mid 1800’s Charles Wheatstone constructed a bit more complicated version of this machine, that was some similar to the figure below. 37 Chapter 4. Applications Figure 4.1: Wheatstone’s reconstruction of von Kempelen’s speaking machine. [9] Taken from Sami Lemmettly.[10] Over time, the development of the synthesizers moved from mechanical to electrical machines, the first introduced by Stewart in 1922. The machine was able to generate single static vowel sounds with two lowest formants, but not any consonants or connected utterances. The first device to be considered as a speech synthesizer was VODER (New York World’s Fair, 1939), inspired by the VOCODER, developed at Bell Laboratories some years before. Figure 4.2: The VODER speech synthesizer. [11] Taken from Sami Lemmettly[10]. 38 Chapter 4. Applications After the demonstration of the potential of VODER for producing artificial speech, the scientific world became more and more interested in speech synthesis. Moving along to the text-to-speech systems, their first occurrence were in 1968 in Japan by Noriko Umeda. It was based on an articulatory model and include a syntactic analysis module with sophisticated heuristics. Since 1970’s and early 1980’s, a lot of commercial text-to-speech products have been introduced. Figure 4.3: Some milestones in speech analysis. Taken from Sami Lemmettly[10]. And finally, we mention here some of the great challenges in the text-to-speech synthesization nowadays: •Text normalization: Heteronyms (The weather was beginning to affect his affect), numbers and abbreviations. •Text-to-phoneme: Text-to-phoneme or grapheme-to-phoneme conversion. •Prosodics and emotional content. 4.1.2 Current TTS engines Actual text-to-speech engines are quite advanced, based on hundred on voice recordings, neural networks. . . some examples of commercial products of tts are: •Acapela Box •Google Text-to-Speech •Cepstral 39 Chapter 4. Applications •ATT natural •Nuance RealSpeak Voices However, we’ll focus on the open source text-to-speech engines and resources: •eSpeak[12]: Originally know as speak (1995), uses a “formant synthesis” method. This allows many languages to be provided in a small size. The speech is clear, and can be used at high speeds, but is not as natural or smooth as larger synthesizers which are based on human speech recordings. •MaryTTS[13]: A multilingual text-to-speech synthesis platform written in Java. Currently supports German, British and American English, French, Italian, Swedish, Russian, Turkish and Telugu (with more languages in preparation). •Festival[14]: Developed by the the centre for speech technology research at the University of Edinburgh, Festival offers a framework for building speech synthesis systems. Also provides tools for build new voices through Carnegie Mellon’s FestVox project. •MBROLA project[15]: Initiated by the TCTS Lab of the Facult´e Polytechnique de Mons (Belgium), its aim is to obtain a set of speech synthesizers for as many languages as possible, and provide them free non-commercial applications. Central to the MBROLA project is MBROLA, a speech synthesizer based on the concatenation of diphones. It takes a list of phonemes as input, together with prosodic information (duration of the phonemes and a piecewise linear description of pitch), and produces speech samples (it is therefore not a TTS synthesizer, since it does not accept raw text as input). This synthesizer is provided for free, for non commercial, non military applications only. 4.1.3 Implementation Due to the language characteristics that Unilan wants to achieve, some of the challenges above mentioned are almost removed, for example: •Heteronyms doesn’t exist, because the desirable lack of ambiguity in the language. •Text-to-phoneme problem: Totally eliminated, one symbol = one grapheme = one phoneme. •Prosody is removed, with no intentionality on the pronunciation tone. 40 Chapter 4. Applications First version of the text-to-speech we used eSpeak, with a new definition of sounds for the Unilan language. Then, the software generated the wav files for each of the 80 phonemes of the language. The wav file silences were trimmed and the tts was done using the final wav files with the following python script: import wx from sys import stdin from time import sleep PHONEMES = [’ba ’, ’be ’, ’bi ’, ’bo ’, ’bu ’, ’ca ’, ’ce ’, ’ci ’, ’co ’, ’cu ’, ’da ’, ’de ’, ’di ’, ’do ’, ’du ’, ’fa ’, ’fe ’, ’fi ’, ’fo ’, ’fu ’, ’ga ’, ’ge ’, ’gi ’, ’go ’, ’gu ’, ’ja ’, ’je ’, ’ji ’, ’jo ’, ’ju ’, ’la ’, ’le ’, ’li ’, ’lo ’, ’lu ’, ’ma ’, ’me ’, ’mi ’, ’mo ’, ’mu ’, ’na ’, ’ne ’, ’ni ’, ’no ’, ’nu ’, ’pa ’, ’pe ’, ’pi ’, ’po ’, ’pu ’, ’ra ’, ’re ’, ’ri ’, ’ro ’, ’ru ’, ’sa ’, ’se ’, ’si ’, ’so ’, ’su ’, ’ta ’, ’te ’, ’ti ’, ’to ’, ’tu ’, ’wa ’, ’we ’, ’wi ’, ’wo ’, ’wu ’, ’ya ’, ’ye ’, ’yi ’, ’yo ’, ’yu ’, ’za ’, ’ze ’, ’zi ’, ’zo ’, ’zu ’] WHITESPACE_PAUSE = .3 # Pause ( seconds ) when a whitespace is read PHONEME_PAUSE = .05 # Pause ( seconds ) between phonemes def main (): # wx initialization app = wx . App ( False ) assert app # remove pyflakes warning sounds = [] for phoneme in PHONEMES : sounds . append ( wx . Sound ( ’ phonemes /’ + phoneme + ’. wav ’)) while True : fst = stdin . read (1) if fst == ’\n’: continue if fst == ’ ’: sleep(WHITESPACE_PAUSE) continue snd = stdin . read (1) audio = sounds [ PHONEMES . index( fst + snd )] audio . Play (wx . SOUND_SYNC ) sleep ( PHONEME_PAUSE ) if __name__ == " __main__ ": main () Listing 4.1: First text-to-speech script However, this first version sounded too unnatural, and some phonemes were very difficult to distinguish from others. Because of that, a second version of the phonemes was generated using the MBROLA synthesizer, by only making a phonemic description of each Unilan symbol (e.g. ba = /ba/, ca = /ca/, za = /Ta/, . . . ). The voice used is also from the MBROLA project (voice es2: Spanish Male (5.1Mb) TCC Communications Corp.). 41 Chapter 4. Applications 4.2.4 Results Two tests have been designed for the speech recognition system: 1. A first test, to confirm that the system recognizes all the phonemes correctly, when given independently. If the system doesn’t pass this test, it’s pointless to proceed with the next one. 2. A second test, generating 100 random words of different lengths and confirming that the system recognizes them correctly. This test is designed with the goal of analyzing if the system is capable of correctly identifying the different phonemes in a word, split them into several samples, and identify a whole word right. For the second test, all the words were generated with a pause between phonemes of 0.03 seconds, and one of the parameters for the AudioMatcher class shown in the annex is the interphoneme separation threshold, that is, how long is a silence for us. The results we hope to see in this tests are: That with no silence recognition is that all the phonemes are recognized individually, but any of the words are recognized correctly. On the other hand, if we set the interphoneme separation threshold to a very high value (in this case more than 0.03 seconds) the results will be the same, because no one word will have enough silence between the phonemes to be identified as two or more phonemes. The value we’re looking for is between 0.00s and 0.03s, so we’ve performed the test from no silence detection to 0.03s in intervals of 0.001s, and the results for the first test are the following: 48 Chapter 4. Applications Figure 4.4: Phoneme errors vs Interphoneme separation As we expected, at the beginning there were zero errors. Then, as we start to detect silences, the own phonemes are splitted into two or more samples, so they are incorrectly recognized. From a interphoneme separation of 0.024s, it seems to recognize all the phonemes again. Now let’s move on to the second test. Figure 4.5: Random word errors vs Interphoneme separation Like the previous test, the results are consistent with what we expected. Again, from 0.024s of interphoneme separation all the words are correctly splitted and recognized. 49 Chapter 4. Applications 4.3 System Font The last application we’ll talk about is the system font for Unilan. A simple but essential piece for the use of the language on all the desktop operating systems. The font is generated with the FontForge open source software, and we’ll use svg files of the Unilan’s symbols to create it. The script and JSON file for creating the svg files are included in Annex B. As a result, 21 svg files of the letters are generated, but for some reason, if we try to build the Unilan’s alphabet font directly from these files into FontForge, some visualization problems appear after exporting the font file. The solution is to open all the svg files into some vector editor (Adobe Illustrator, Inkscape) and save them again as new files. For some strange reason, the files we’ve generated before were causing problems in FontForge, maybe the direction of the strokes are reorganized or the structure of the file is modified somehow after save the file again. Figure 4.6: Building the Unilan’s font in FontForge After that, the Unilan font is ready to be built in FontForge. The way we did it for the Unilan’s symbol to appear is to align the vowels to the left part of the available space for the letter, and the consonants to the right side. 50 Chapter 4. Applications A example of the resultant font (the word ‘butano’) is shown below in a OS X text editor: Figure 4.7: Unilan’s font in text editor If we consider that the spaces between graphemes are too big, it would be easy to adjust with FontForge in any moment. To end, an attempt was made to include the Unilan’s font in google docs, but it was not possible because its font ecosystem is closed by now. The only option is a google docs plugin that transforms pair of letters to images representing its Unilan’s symbol (a pretty useless approach that was discarded after its development). 51 Chapter 5 Discussion & Conclusions As we’ve seen, the work presented covers from theoretical analysis to technical issues. To begin, we’ve adapted techniques that were described in the 50s together with linguistic analysis of natural languages that have served us to make a first proposal of a codification for a new constructed language, initially focusing on the prefix codes, for then take a look to the synchronization loss problem, and therefore to the self-synchronizing codes. To complement the theoretical part, implementations of the different algorithms have been developed in python also. In the applications part, in addition to the implementations that have been done, the fields of voice synthesization and speech recognition have been studied, obtaining an overview of the current situation on these fields, as well as of some of the problems that the automatic language processing tries to deal with. In the speech synthesis part we’ve seen that not always using what Google uses (eSpeak) is going to give us the best result, al least at first. We’ve chosen for a more simpler approach using existing voices from the MBROLA project, giving us decent results in voice synthesization in a fast way at least. With the study done we’ve been able to detect the phonemes that are likely to be confused when using the synthesizer, focusing the future upgrades of the system on these sounds (making the sounds clearer, proposing possible changes to the language design, etc.). By other side, the fact of doing the study has led to the design and implementation of a webbased plataform for the realization of this via online, so we’ve dealt with the web development and the use of frameworks for this task also, like for example in this case, Django. 53 Chapter 5. Discussion & Conclusions In the speech recognition field, the techniques used today have been studied, watching how the hidden Markov models and the neuronal networks are the most used models in the engines existent nowadays. As it happened with the synthesis system, we’ve chosen a simpler approach for the realization of this task, and a development of a system using the techniques mentioned before wouldn’t be feasible for the lack of time. As we commented in its implementation, when detecting and dividing an audio we can lose some of the information of the phoneme we’re trying to identify, that is why we have used the CUDA technology that Nvidia provides us for the mass data processing, doing a sort of massive matching with different displacements of the obtained samples over the original phonemes, doing all the comparisons practically without cost, at once. To end, the development of the system font, that has brought some technical problems with it, like the strange problem of the svg files when trying to use them directly with FontForge, but that had a simple solution, giving as result the last application developed, that still being the most easier to develop, it’ll be the most used application for the Unilan language initially. To finalize and as future work for the language, the following topics are still open: •The further study of the synthesizer study results, identify the most problematic phonemes and try to fix them. By other side, keep studying other possible solutions using other engines, for example and again, eSpeak. •The analysis of the possibility of creating an acoustic model of Unilan, for its possible use in some of the studied solutions in the speech recognition part, like sphinx. •Also contemplate the possibility of improving the developed algorithm, doing a deeper study before of the algorithm (noisy samples, samples spoken by persons, etc.). 54 Chapter 5. Discussion & Conclusions Como hemos visto, el trabajo desarrollado aqu´ı cubre desde an´alisis te´orico a la parte m´as t´ecnica. Para empezar, hemos adaptado t´ecnicas que fueron descritas en los a˜nos 50 en conjunto con an´alisis sobre ling¨u´ıstica en lenguajes naturales que nos han servido para realizar una primera propuesta de codificaci´on para un nuevo lenguaje artificial, en un principio girando en torno a los c´odigos libre de prefijo, para en un segundo plano tambi´en ver el problema de la p´erdida de sincronizaci´on, y por ende los c´odigos auto sincronizantes. Para complementar la parte te´orica, tambi´en se han realizado implementaciones de los distintos algoritmos en python. En la parte de aplicaciones, adem´as de las implementaciones que se han llevado a cabo, se han estudiado los campos de la sintetizaci´on y reconocimiento de voz, obteniendo una visi´on general de la situaci´on actual (el estado de la t´ecnica) en estos campos, as´ı como de algunos de los problemas con los que intenta lidiar el procesamiento autom´atico del lenguaje. En la sintetizaci´on de voz hemos visto por ejemplo que no siempre al utilizar lo que Google utiliza (eSpeak) vamos a obtener un mejor resultado, al menos no de primeras. Hemos optado por un enfoque mucho m´as f´acil utilizando voces ya existentes del proyecto MBROLA, pero que al menos nos ha permitido obtener de manera “r´apida” unos resultados decentes en sintetizaci´on. Con el estudio realizado hemos podido detectar los fonemas que m´as se confunden a la hora de poner a prueba el sintetizador, pudiendo focalizar las posibles mejoras futuras del sistema en esos sonidos (haciendo que estos sonidos suenen m´as claro, planteando posibles cambios en el dise˜no del lenguaje, etc.). Por otra parte, el mero hecho de realizar el estudio ha tra´ıdo como consecuencia el dise˜no e implementaci´on de un peque˜no sitio web para la realizaci´on de ´este v´ıa online, por lo que se ha lidiado tambi´en con el desarrollo web y la utilizaci´on de frameworks destinados para ello, como es en ´este caso, Django. En el reconocimiento de voz, se han vuelto a estudiar las t´ecnicas m´as usadas actualmente, viendo como los modelos ocultos de Markov y las redes neuronales son los modelos m´as usuales entre los motores existentes a d´ıa de hoy. Al igual que pas´o con el sistema de s´ıntesis, hemos optado por un enfoque m´as simple para la realizaci´on de ´esta tarea, ya que un desarrollo de un sistema utilizando las t´ecnicas nombradas anteriormente no ser´ıa viable por falta de tiempo principalmente. Como comentamos en su implementaci´on, a la hora de detectar y dividir un audio podemos perder parte de la informaci´on del fonema que intentamos identificar, es por ello que se ha hecho uso de la tecnolog´ıa CUDA que Nvidia nos provee para el procesamiento masivo de 55 Chapter 5. Discussion & Conclusions datos, haciendo una especie de matching masivo con distintos desplazamientos de las muestras obtenidas sobre los fonemas originales, haciendo todas las comparaciones pr´acticamente sin costo, a la vez. Por ´ultimo, el desarrollo de la fuente, que ha tra´ıdo consigo algunos problemas t´ecnicos, como el extra˜no problema que daban los ficheros svg al tratar de utilizarlos directamente con FontForge, pero que ten´ıan una soluci´on sencilla al fin y al cabo, dando como resultado la ´ultima aplicaci´on desarrollada, que a´un siendo la m´as f´acil de desarrollar, ser´a la m´as utilizada en un principio para el uso del lenguaje Unilan. Para finalizar y como trabajo futuro para el lenguaje, siguen abiertos los siguientes frentes: •El estudio en profundidad de los resultados del estudio realizado para el sistema de sintetizaci´on, identificar los fonemas m´as problem´aticos e intentar solucionarlos. Por otro lado seguir el estudio de otras posibles soluciones m´as elaboradas utilizando por ejemplo, de nuevo, eSpeak. •El an´alisis de la posibilidad de crear un modelo ac´ustico de Unilan, para su posible uso en algunas de las soluciones estudiadas en la parte de reconocimiento de voz, como sphinx. •Tambi´en contemplar la posibilidad de mejorar el algoritmo existente desarrollado, realizando previamente un estudio de campo con m´as profundidad (muestras con ruido, muestras habladas por personas, etc). 56 Bibliography [1] C. E. Shannon, “A mathematical theory of communication,” ACM SIGMOBILE Mobile Computing and Communications Review, vol. 5, no. 1, pp. 3–55, 2001. [2] D. A. Huffman et al., “A method for the construction of minimum redundancy codes,” Proceedings of the IRE, vol. 40, no. 9, pp. 1098–1101, 1952. [3] C. E. Shannon and W. Weaver, “The mathematical theory of information,” 1949. [4] “How many words do I need to know? The 95/5 rule in language learning, Part 2/2.” http://www.lingholic.com/how-many-words-do-i-need-to-know-the-955-rulein-language-learning-part-2/ Accessed: 2015-09-01. [5] E. N. Gilbert and E. F. Moore, “Variable-length binary encodings,” Bell System Technical Journal, vol. 38, no. 4, pp. 933–967, 1959. [6] T. J. Ferguson and J. H. Rabinowitz, “Self-synchronizing huffman codes (corresp.),” IEEE Transactions on Information Theory, vol. 30, no. 4, pp. 687–693, 1984. [7] M. Titchener, “Digital encoding by means of new t-codes to provide improved data synchronisation and message integrity,” IEE Proceedings E (Computers and Digital Techniques), vol. 131, no. 4, pp. 151–153, 1984. [8] M. Titchener, “Generalised t-codes: extended construction algorithm for selfsynchronising codes,” IEE Proceedings-Communications, vol. 143, no. 3, pp. 122–128, 1996. [9] K. Ishizaka and J. L. Flanagan, “Synthesis of voiced sounds from a two-mass model of the vocal cords,” Bell system technical journal, vol. 51, no. 6, pp. 1233–1268, 1972. [10] S. Lemmettly, “Review of Speech Synthesis Technology,” 1999. [11] D. H. Klatt, “Review of text-to-speech conversion for english,” The Journal of the Acoustical Society of America, vol. 82, no. 3, pp. 737–793, 1987. [12] “eSpeak: Speech Synthesizer.” http://espeak.sourceforge.net Accessed: 2015-09-01. 57 Appendix A. STT Implementation # Copy data to gpu drv.memcpy_htod(source_gpu, source_data) drv.memcpy_htod(phonemes_gpu, self.phoneme_data) drv.memcpy_htod(indexes_gpu, self.indexes) drv.memcpy_htod(length_gpu, length) # Execute kernel grid = (total_phonemes, 1, 1) func = CUDA_CODE.get_function("""phoneme_match""") func(dest_gpu, source_gpu, phonemes_gpu, indexes_gpu, length_gpu, block=(256, 1, 1), grid=grid) # Copy result from gpu drv.memcpy_dtoh(dest_data, dest_gpu) # Free gpu memory source_gpu.free() dest_gpu.free() phonemes_gpu.free() indexes_gpu.free() result = np.array([min(x) for x in dest_data]) return PHONEMES[result.argmin()] def main(): parser = argparse.ArgumentParser(description=’Unilan voice recognizer’) parser.add_argument(’file’, metavar=’audio_file’, nargs=1, help=’audio file’) args = parser.parse_args() audio = Audio(args.file[0]) matcher = AudioMatcher() print matcher.match(audio) if __name__ == ’__main__’: 6 Appendix A. STT Implementation main() And the CUDA kernel (kernels.cu): __global__ void phoneme_match(int *dest, int *source, int *phonemes, int *indexes, int *size) { int len = size[0]; int length = indexes[blockIdx.x + 1] - indexes[blockIdx.x]; int result1 = 0; int result2 = 0; float compare_index = indexes[blockIdx.x]; float index_inc = len / (float)length; for(int i = 0; i < len - threadIdx.x; i++) { result1 += abs(source[i + threadIdx.x] - phonemes[(int)compare_index]); result2 += abs(source[i] - phonemes[(int)(compare_index + threadIdx.x * index_inc)]); compare_index += index_inc; } dest[blockIdx.x * 512 + threadIdx.x * 2] = result1; dest[blockIdx.x * 512 + threadIdx.x * 2 + 1] = result2; } 7 Appendix B SVG file generation scripts File UnilanSVG.m: function UnilanSVG (dim) % unilat.json specifies the unilan version of the latin character map, % upon which unilan builds. % each polygon line in a letter is a closed polygon in the width x height grid. % it goes horizontal first, then vertical, and so on until it closes. % positive values mean right or down movements, negative mean left or up movements. folder = ’./’; u = loadjson (’unilat.json’); if (exist (’dim’,’var’)) u.dim = dim; endif u.width = u.width * u.dim; u.height = u.height * u.dim; for idSym = 1:length (u.symbol) l = u.symbol{idSym}.letter % letter p = u.symbol{idSym}.polygon; % shape clear pol; if (~iscell (p)) % letters with a single polygon are 9 Appendix B. SVG file generation scripts for idDim = 1:size (p, 1) % read as a vector, not a cell array pol{idDim} = p(idDim, :); endfor p = pol; endif f = fopen ([folder l ’.svg’],’wt’); % write svg file fprintf (f, ’<svg width="%d" height="%d" viewBox="0 0 %d %d">\n’, u.width, u.height, u.width, u.height); fprintf (f, ’<path stroke-width="0" d="’); for idPol = 1:length (p) e = p{idPol}; fprintf (f, ’M%d,%d’, e(1) * u.dim, e(2) * u.dim); d = ’v’; for idLin = 3:length (e) if (d == ’h’) % alternate directions d = ’v’; % first horizontal, then vertical else d = ’h’; endif fprintf (f, ’ %c%-d’, d, e(idLin) * u.dim); endfor fprintf (f, ’z ’); endfor fprintf (f, ’" fill-rule="evenodd" />\n’); fprintf (f, ’</svg>’); fclose (f); endfor endfunction And the unilat.json (’unilat’ coming from Unilan-latin characters) file: { "dim" : 5, "width" : 3, "height": 5, "symbol": [ { "letter": "A", 10 Appendix B. SVG file generation scripts "polygon": [ [ 0, 0, 2, 5,-1,-4,-1] ] }, { "letter": "B", "polygon": [ [ 0, 0, 3, 5,-3], [ 1, 1, 1, 1,-1], [ 1, 3, 1, 1,-1] ] }, { "letter": "C", "polygon": [ [ 0, 0, 3, 1,-2, 3, 2, 1,-3] ] }, { "letter": "D", "polygon": [ [ 0, 0, 3, 5,-3], [ 1, 1, 1, 3,-1] ] }, { "letter": "E", "polygon": [ [ 0, 0, 2, 1,-2], [ 0, 2, 2, 1,-2], [ 0, 4, 2, 1,-2] ] }, { "letter": "F", "polygon": [ [ 0, 0, 3, 1,-2, 1, 1, 1,-1, 2,-1] ] }, { 11 Appendix B. SVG file generation scripts "letter": "G", "polygon": [ [ 0, 0, 3, 1,-2, 3, 1,-2, 1, 3,-3] ] }, { "letter": "I", "polygon": [ [ 0, 0, 2, 1,-2], [ 0, 4, 2, 1,-2] ] }, { "letter": "J", "polygon": [ [ 0, 0, 3, 5,-3,-1, 2,-3,-2] ] }, { "letter": "L", "polygon": [ [ 0, 0, 1, 4, 2, 1,-3] ] }, { "letter": "M", "polygon": [ [ 0, 0, 3, 5,-1,-4,-1, 4,-1] ] }, { "letter": "N", "polygon": [ [ 0, 0, 1, 2, 1,-2, 1, 5,-1,-2,-1, 2,-1] ] }, { "letter": "O", "polygon": [ [ 0, 0, 2, 5,-2,-1, 1,-3,-1] 12 Appendix B. SVG file generation scripts ] }, { "letter": "P", "polygon": [ [ 0, 0, 3, 3,-2, 2,-1], [ 1, 1, 1, 1,-1] ] }, { "letter": "R", "polygon": [ [ 0, 0, 3, 5,-1,-2,-1, 2,-1], [ 1, 1, 1, 1,-1] ] }, { "letter": "S", "polygon": [ [ 0, 0, 3, 1,-2, 1, 2, 3,-3,-1, 2,-1,-2] ] }, { "letter": "T", "polygon": [ [ 0, 0, 3, 5,-1,-4,-2] ] }, { "letter": "U", "polygon": [ [ 0, 4, 1,-4, 1, 5,-2] ] }, { "letter": "W", "polygon": [ [ 0, 0, 1, 4, 1,-4, 1, 5,-3] ] }, 13 Appendix B. SVG file generation scripts { "letter": "Y", "polygon": [ [ 0, 0, 1, 2, 1,-2, 1, 5,-1,-2,-2] ] }, { "letter": "Z", "polygon": [ [ 0, 0, 3, 3,-2, 1, 2, 1,-3,-3, 2,-1,-2] ] } ] } 14