Using N-gram statistics for cryptic language word saegmentation, auto-completion and auto-correction

This thesis aims to deal with the issues of auto-completing and auto-correcting commands formed using the syntax of an artificial language called Cryptic. This particular language is a proprietary language defined and put into production by the multinational company Amadeus SAS France. In spite of the fact that Cryptic is an artificial language the techniques used in natural language processing are used trough out this thesis. Data available in Amadeus Cryptic logs is composed of unsegmented commands, therefore no notion of words was present in the command logs. Taking this as starting point reasonable approach is to build n-gram statistics at symbol level, providing estimators on relations between symbols. On the other hand one important attribute of this system is that each command is of a finite length which implies that every command starts with a special symbol Ш (Cyrillic symbols are used to denote any special character that supplements Cryptic alphabet). This simplifies the model into a tree structure, instead of a graph, and the root of this structure is a node with label Ш. This tree structure is made as a combination of B+ trees, FP trees and hash-based indexes, to facilitate various kinds of fast searches that are needed in the algorithms used in building of this system. Based on this tree structure a majority vote procedure is used to segment commands into words and to extract a dictionary of Cryptic language in an automated way. Majority voting bases its decision on various segmentation indicators such as Shanon’s mutual information function, entropy value of an n-gram, probability variance per symbol pair, etc. Once a dictionary is formed other statistics based on a notion of language words can be produced and used to detect errors and produce corrected output. Validation of a subsystem dedicated for command segmentation is computed on the corpus of English language, due to the fact that corpus of segmented and labelled date of Crytpic commands doesn’t exist. Results obtained this way are taken as proof of concept and any decrease of precision in segmentation on Cryptic commands (which unfortunately at the moment can’t be measured) is assigned to the larger amount of ‘randomness’ in the language creation, since the language was partially created by various teams over a period of more than 20 years and lacks any formal standardization. Validation on auto-complete and auto-correct capabilities is done on the portion of the data logs that is not used in the training phase.

Questa tesi si propone di affrontare i problemi di auto-completamento e comandi di auto-correzione formati utilizzando la sintassi di una lingua artificiale chiamata Cryptic. Questo linguaggio particolare, è un linguaggio proprietario definito e messo in produzione dalla multinazionale Amadeus SAS Francia. Nonostante il fatto che Cryptic è una lingua artificiale le tecniche utilizzate nella elaborazione del linguaggio naturale sono utilizzati attraverso questa tesi. I dati disponibili in Amadeus registri di Cryptic è composto di comandi non segmentati, quindi nessuna idea di parole era presente nei registri di comando. Prendendo questo come punto di partenza approccio ragionevole è quello di costruire le statistiche n-gram a livello di simbolo, fornendo stimatori sulle relazioni tra i simboli. D'altra parte un attributo importante di questo sistema è che ogni comando è di una lunghezza finita che implica che ogni comando inizia con un simbolo speciale Ш (simboli cirillici vengono utilizzati per indicare qualsiasi carattere speciale che integra alfabeto Cryptic). Questo semplifica il modello in una struttura ad albero, invece di un grafico, e la radice di questa struttura è un nodo con etichetta Ш. Questa struttura ad albero è realizzata come una combinazione di alberi B +, alberi FP e indici basati su hash, per facilitare vari tipi di ricerche veloci che sono necessari in algoritmi utilizzati nella costruzione di questo sistema. Sulla base di questa struttura ad albero una procedura maggioranza è usato per comandi segmento in parole e per estrarre un dizionario di linguaggio criptico in modo automatizzato. Basi di voto a maggioranza la sua decisione su vari indicatori di segmentazione come la funzione di Shanon reciproca informazione, il valore di entropia di un n-gram, probabilità varianza per coppia simbolo, ecc Una volta che un dizionario è formata altre statistiche sulla base di una nozione di parole della lingua possono essere prodotti e utilizzato per rilevare gli errori e produrre output corretto. La convalida di un sottosistema dedicato per la segmentazione comando viene calcolata sul corpus di lingua inglese, a causa del fatto che il corpus di data segmentato ed etichettatura dei comandi Crytpic non esiste. I risultati così ottenuti sono presi come prova di concetto e qualsiasi diminuzione di precisione nella segmentazione comandi criptici (che purtroppo al momento non può essere misurata) è assegnato alla maggiore quantità di 'casualità' nella creazione lingua, poiché la lingua parzialmente creato da diversi gruppi per un periodo di più di 20 anni e manca qualsiasi normalizzazione formale. Convalida funzionalità di completamento automatico e correzione automatica avviene sulla parte dei tronchi di dati che non viene utilizzato nella fase di addestramento.