Algorithmen und Datenstrukturen · Senior · Frage 43 von 75
Welcher Ansatz beantwortet „steht dieses Wort im Wörterbuch?“ für Millionen Wörter mit dem wenigsten Speicher, wenn seltene falsch Positive in Ordnung sind?
- 1Ein Trie aller Wörter
- 2Ein sortiertes Array mit binärer Suche
- 3Ein Bloom-Filter
Antwort zeigen
Richtige Antwort: Ein Bloom-Filter
Erklärung
Ein Bloom-Filter braucht etwa 10 Bits pro Wort für 1 % falsch Positive, unabhängig von der Wortlänge. Ein Trie oder ein sortiertes Array speichert die Wörter selbst, was viel mehr Speicher braucht.