Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-25099
Titel: | Lexicon access on parallel machines |
VerfasserIn: | Duda, Markus |
Sprache: | Englisch |
Erscheinungsjahr: | 1994 |
Quelle: | Saarbrücken, 1994 |
Kontrollierte Schlagwörter: | Künstliche Intelligenz |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Forschungsbericht (Report zu Forschungsprojekten) |
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. |
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 |
Datum des Eintrags: | 22-Jul-2011 |
Fakultät: | SE - Sonstige Einrichtungen |
Fachrichtung: | SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
report_10_94.pdf | 206,09 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.