Hallo,
ich möchte in einem großen Dokument die kleinste Fenstergröße finden, innerhalb derer vorgebbare Wörter in Summe (eventuell gewichtete Summe) mindestens n-Mal vorkommen.
Könnte mir jemand einen Tipp geben, nach welchen Schlagwörtern ich bezüglich dieses Problems bei Google suchen könnte?
Gruss Marco
Hallo Marco,
folgende Idee:
Betrachten wir das Dokument als Liste von Wörtern. Bilden wir die Wörter auf ihr Gewicht ab (oder einfach auf 0 oder 1), dann besteht das Problem darin, die kleinste zusammenhängende Subliste mit Summe>=n zu finden.
Die Summe einer Subliste lässt sich recht einfach mit der „Integralliste“ berechnen. Die Integralliste kann aufgestellt werden, indem die Gewichte aller vorhergehenden Elemente addiert werden (also insgesamt in linearer Laufzeit). Also integralliste[0] = element[0]. integralliste[1] = element[0] + element[1] = integralliste[0] + element[1]. integralliste[2] = integralliste[1] + element[2] usw. Dann ist die Summe einer Subliste von j bis i genau Integralliste[i] - Integralliste[j-1].
Also wir laufen durch die Liste und berechnen dabei die Integralliste. Wir brauchen aber gar nicht die Liste, sondern wir wollen zu einem beliebigen Element e[i] wissen, wie weit wir zurückgehen müssen, damit wir Summe n bekommen. Also speichern wir die Elemente der Integralliste in einer Map von integralWert->Index. Dabei können wir kleinere Indizes mit höheren überschreiben. Wenn wir jetzt am Element e[j] mit dem Integralwert in sind, dann schauen wir in der Map nach dem Index mit dem Integralwert in-n. Falls es den nicht gibt, dann prüfen wir kleinere Werte (entspricht größeren n). Der Abstand dieses Indexes von j ist dann die Größe des Fensters mit mindestens n gesuchten Wörtern, dass bei e[j] endet. Wenn das kleiner ist als das bisher gefundene Fenster, dann ersetzen wir dieses.
Insgesamt entsteht eine lineare Laufzeit. Theoretisch könnte man den Anfang der Map auch nach einer Weile verwerfen (wir müssen ja nur n Elemente zurückgehen können). Das Optimieren der Strategie überlasse ich aber dir.
Nico