Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25099
Titel: Lexicon access on parallel machines
Verfasser: Duda, Markus
Sprache: Englisch
Erscheinungsjahr: 1994
Quelle: Saarbrücken, 1994
SWD-Schlagwörter: Künstliche Intelligenz
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: 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.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-40014
hdl:20.500.11880/25155
http://dx.doi.org/10.22028/D291-25099
Schriftenreihe: Vm-Report / Verbmobil, Verbundvorhaben, [Deutsches Forschungszentrum für Künstliche Intelligenz]
Band: 10
SciDok-Publikation: 22-Jul-2011
Fakultät: Sonstige Einrichtungen
Fachrichtung: SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
Fakultät / Institution:SE - Sonstige Einrichtungen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
report_10_94.pdf206,09 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.