Partitionieren einer (String oder Integer) in n-Elemente von min (Länge oder Wert) von 2

Question

Ich habe eine Liste von ~ 120'000 Strings verschiedener Länge (von 4 bis 27) und ich möchte überprüfen, ob diese Zeichenfolgen bestehen aus Sub-Strings, die in einem Wörterbuch existieren, und diese Sub-Strings können verschiedene Längen haben und mindestens 2 Zeichen lang sein.

Zum Beispiel würde eine 9 Zeichen lange Zeichenfolge in min 2 Sub-Strings unterteilt werden. Und natürlich muss ich alle möglichen Kombinationen

astring = '123456789' 
# possible divisions 
2 sub-strings = [['12','3456789'],['1234567','89'],['123','456789'],...] 
3 sub-strings = [['12345', '67','89'],['1234','567','89']...] 
4 sub-strings = [['12','34','56','789'],['12','34','567','89']...] 

I code below at this address gefunden und nach Ergebnisse nach Anforderungen Ablehnung Ich habe, was ich brauche, aber ich bin mir nicht sicher, ob es nicht zu langsam ist. Bei einer 18 Zeichen langen Zeichenfolge dauert es 2 Sekunden, um eine Zeichenfolge zu verarbeiten (Stunden für die gesamte Liste). Bei einer 18 Zeichen langen Saite bekomme ich 1596 gute Scheiben von 131072, also sind 98% nutzlos. Gibt es einen schnelleren Weg, es zu tun?

from itertools import chain, combinations 

def partition(iterable, chain=chain, map=map): 
    s = iterable if hasattr(iterable, '__getslice__') else tuple(iterable) 
    n = len(s) 
    first, middle, last = [0], range(1, n), [n] 
    getslice = s.__getslice__ 
    return [map(getslice, chain(first, div), chain(div, last)) 
      for i in range(n) for div in combinations(middle, i)] 
some_string = '12345678' 

for xyz in xrange(100): 
    for x in partition(some_string): 
     if (any(len(astring) == 1 for astring in x)): 
      continue 
     if len(x) == 1: 
      continue 
     # otherwise do something here 

in Antwort auf eyquem Kommentar zu spezifizieren:

ein Wörterbuch der Wörter in der japanischen haben (japanische verwenden keine Leerzeichen) und viele Wörter der Länge von 4 Zeichen oder länger Verbindung Wörter aus kürzeren Wörtern. Ich möchte diese Wörter herausfiltern, die in kürzere Wörter aufgeteilt werden können. Später könnte ich die Liste durchgehen und sicherstellen, dass das Schneiden von Wörtern semantisch sinnvoll ist.

Dieser Ansatz ist eine Art brutale Kraft, die ich für einfacher hielt und die ich anstelle einer logischeren, aber komplizierteren For-Schleife mit begrenzter Rekursion verwenden könnte. von links starten und der Suche nach möglichst langen Wort ...

Grüße Bart

Answer 1

Ich bin nicht sicher, ob das hilft, aber Sie könnten versuchen, eine modifizierte radix tree implementieren.