Lexicon access on parallel machines

Abstract

To communicate with a computer in spoken language is an unattained challenge of Artificial Intelligence (AI) and Computational Linguistics. To solve such problems linguistic knowledge has to be combined with programming methods of AI and modern computer architectures. We will show how the complexity of linguistic processes can be handled by taking advantage of parallel architectures. In particular, speech systems where most lexicon queries are extremely underspecified suffer from the problem that the access to the lexicon module turns out to be a bottleneck. We introduce the search problem over a given lexicon and compute its time complexity for two different encodings. With the help of a space consuming encoding we define a total order over a lexicon, and, having a total order, logarithmic time becomes valid for the complexity of sequential lexicon search. Next, we will speed up the search by parallelisation, making use of the paracomputer. Last, we describe a practical approach to the parallelisation of a lexicon module with the aim to maximize the throughput.

Lexikalische Einträge werden als gerichtete Graphen repräsentiert. Unter der Annahme, dass die für die Suche relevanten Teile dieser Graphen sich auf Bäume mit einer festen Maximaltiefe reduzieren lassen, wird ein Suchalgorithmus angegeben, der eine zu erwartende zeitliche Komplexität, linear zur Anzahl der lexikalischen Einträge, besitzt. Die Kodierung der lexikalischen Einträge als vollständige Bäume erlaubt die theoretisch mögliche Berechnung der Suche mit einer maximalen Anzahl von Prozessoren im Paracomputermodell in einem Schritt. Ein anderes Modell ergibt sich aus der Zerlegung des einen lexikalischen Eintrag repräsentierenden Baumes in die Menge seiner Pfade. Mit einer Numerierungsvorschrift für Pfade lässt sich nun eine totale Ordnung über alle Pfade aller lexikalischen Einträge definieren, was eine Suche in logarithmischer Zeit ermöglicht. Auf der Basis der Pfadzerlegung und -numerierung wird eine Pipeline-Architektur entworfen, die die Suche im Lexikon mit maximalem Durchsatz auf eine gegebene Anzahl von Prozessoren mit dem Ziel optimaler Lastverteilung realisiert.