Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » effizientes String Nachschlagen
Autor
Universität/Hochschule J effizientes String Nachschlagen
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Themenstart: 2021-05-12

Hallo, Gegeben ist folgendes Problem: Man bekommt eine Liste von Strings die entweder aus \(0\) und \(1\) bestehen oder zusätzlich ein \(*\) am Ende tragen. Nun bekommt man als Eingabe eine weitere List von Strings, die nur aus \(0\) und \(1\) bestehen. Man soll für jeden String aus der zweiten List prüfen, ob er gültig ist. Dabei ist ein String gültig genau dann wenn es einen String in der ersten Liste gibt, der mit ihm exakt übereinstimmt oder wenn es einen String in der ersten Liste gibt, der mit \(*\) endet und dessen \(0\) und \(1\) Sequenz ein präfix des zu prüfenden Strings ist. Also wäre wegen dem String \(011*\) der String \(01101\) gültig. Mein naiver Ansatz ist es zwei Datenstrukturen für normale Strings und die \(*\) anzulegen und dann für jeden eingabe String zu prüfen, ob es einen String in den beiden Datenstrukturen gibt, der ihn als gültig verifiziert. Allerdings ist der sehr langsam und die einzige beschleunigung die mir einfällt ist, die Datenstrukturen vorher zu sortieren und dann binär zu suchen. Hat jemand eine andere Verbesserungsidee? Danke!


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6908
Wohnort: Niedersachsen
  Beitrag No.1, eingetragen 2021-05-12

Wie wäre es, die erste Liste in einem Baum zu speichern. Jeder innere Knoten besteht aus einer Folge von 0 und 1 und jedes Blatt aus einer Folge von 0 und 1 und am Ende ein Zeichen "." oder "*". Jeder Knoten besteht dabei aus der String-Kette seines Elternknotens und einem weiteren Zeichen. Die Wurzel ist der leere String. Hat ein Knoten ein *-Kind, so müssen die anderen Kinder nicht gespeichert werden.


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2286
  Beitrag No.2, eingetragen 2021-05-12

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\) Eine detailliertere Variante: Die Knoten des Baums sind mit ?, . oder * beschriftet, und haben jeweils ein optionales 0-Kind und ein optionales 1-Kind, welche Bäume derselben Form sind. Der leere Baum akzeptiert dann kein einziges Wort, ein Baum mit *-Wurzel akzeptiert alle Worte, ein Baum mit .-Wurzel akzeptiert das leere Wort, darüber hinaus akzeptiert jeder Baum, dessen Wurzel ein 0-Kind hat, alle Wörter $0\alpha$, für die $\alpha$ von diesem Kind akzeptiert wird, und jeder Baum, dessen Wurzel ein 1-Kind hat, alle Wörter $1\alpha$, für die $\alpha$ von diesem Kind akzeptiert wird. (und sonst wird nichts akzeptiert) \(\endgroup\)


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1825
  Beitrag No.3, eingetragen 2021-05-13

Hallo dvdlly! Es gibt in der Informatik String/Textsuche Algorithmen. Ohne jetzt die Implementierung genau im Gedächtnis zu haben... siehe auch https://de.wikipedia.org/wiki/String-Matching-Algorithmus Viele Grüße Ronald


   Profil
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Beitrag No.4, vom Themenstarter, eingetragen 2021-05-14

Danke für eure Ideen!


   Profil
dvdlly hat die Antworten auf ihre/seine Frage gesehen.
dvdlly hat selbst das Ok-Häkchen gesetzt.
dvdlly wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]