Wort in Text mit >100.000 Wörter finden

[DerMitWörtern]

Hallo Leute

Ich habe ein Textfile mit Synonymen. Insgesamt sind es etwa ca. 120.000 Wörter die durch ; getrennt sind.
Ein kleiner Auszug:

Buchführung;Buchhaltung
Metabolismus (fachsprachlich);Stoffwechsel
schütteln;rütteln
Konferenzraum;Sitzungszimmer

Nun möchte ich, dass der Anwender ein Wort eingibt und ihm dann die Synonyme dazu angezeigt werden. Ich bin mir aber nicht sicher wie ich das nun am besten angehe.
Die einfachste Möglichkeit wäre jedes mal wenn ein Wort eingegeben wird das File einzulesen bis das Wort gefunden wird. Also etwa so:

while (Wort nicht gefunden){
   String wort = nächstes Wort einlesen
   if(wort = gesuchtesWort)
       break;
}

Allerdings habe ich die Befürchtung, dass das bei der Menge an Worten relativ lange dauern kann.

Eine andere Möglichkeit die mir eingefallen ist wäre beim Programmstart einen Trie wie hier beschrieben aufzubauen. Damit würde es wohl schneller gehen ein Wort zu finden, der Implementierungsaufwand steigt aber deutlich.

Was meint ihr dazu?

 

[faetzminator]

Eine andere Möglichkeit die mir eingefallen ist wäre beim Programmstart einen Trie wie hier beschrieben aufzubauen. Damit würde es wohl schneller gehen ein Wort zu finden, der Implementierungsaufwand steigt aber deutlich.

Ich würde zu dem tendieren.

 

[Final_Striker]

Was meint ihr dazu?

Eine Map. Mir dem Wort als Key und der Synonymliste als Value.

 

[parabool]

Das einfachste wäre, das Textfile in eine (embedded) Datenbank einzulesen und dann
per SQL die Synonyme zu suchen.

z.B.
Eine Tabelle für die Wörter -> id | Wort
Eine Tabelle für die Verknüpfungen id | id_synonym

Warum ein Trie? Die Synonyme sind doch fest eineinder zugeordnet, eine Ähnlichkeitssuche
greift hier gar nicht.

 

[timbeau]

Warum sollte Trie schneller sein? Ist ja nur die Speicherverwaltung.

Außerdem braucht man dann immernoch Synonyme.

Die schlechteste Möglichkeit ist es, ein File jedes Mal neu einzulesen.

1x einlesen. Die Synonyme in einer HashMap z.B. unter dem Wort speichern.

Um Platz zu sparen, könnte man auch jedes Wort mit einem int kodieren und dann hast du nur noch sowas wie
K<>Values
schütteln <> 356, 4590, ....

und guckst in einer 2. Map nach.

Ich weiß nicht, was die JVM mit gleichen Strings in diesem Fall macht. Ich nehme an, jeder wird einzeln gespeichert. Durch die Kodierung kann man alle gleichen Strings auf einen int mappen.


@SQL: Willst du schnell nach was suchen, nimm keine DB.

 

[parabool]

@SQL: Willst du schnell nach was suchen, nimm keine DB.

Ja, Implementierung mittels Hashmap o.Ä. geht vllt. schneller (Programmieraufwand).

 

[Ark]

Ich tendiere grundsätzlich ebenfalls zu Tries: Radix tree - Wikipedia, the free encyclopedia

Aber mal ein paar grundsätzliche Fragen, die sehr wesentlichen Einfluss auf Verwendbarkeit, Speicherverbrauch und Geschwindigkeit haben können:

• Zeigt immer ein Wort auf genau eine Menge von Synonymen? Oder gibt es für ein Wort mehrere mögliche Synonymemengen? So gibt es ja z.B. einmal das Wort "umfahren" und dann noch das Wort "umfahren", dass so ziemlich das krasse Gegenteil zu ersterem bedeutet.
• Können alle Wörter jeweils sowohl Schlüssel als auch Wert sein? Oder gibt es Wörter, auf die nur verwiesen wird, die man aber nicht nachschlagen kann?
• Was ist wichtiger: Geschwindigkeit beim Nachschlagen oder Geschwindigkeit beim Ändern? Muss sich so ein Wörterbuch überhaupt ändern können, nachdem es erstellt wurde?

Ark

 

[parabool]

ok, Radix tree soll ev. verwendet werden um ein Wort, dem Synonyme zugeordnet sind, erstmal zu finden.
Falsch verstanden.

Können alle Wörter jeweils sowohl Schlüssel als auch Wert sein?

id|wort
-------
1 |domizil
2 |haus
3 |buchführung
4 |wohnung
..

id|id_synonym
--------------
1 |2
1 |4
..