Suchen Trennzeichen/Trennzeichen in Listen von Zeichenfolgen

Question

Ich versuche, Trennzeichen in einer Datei zu finden, die Separatoren haben kann oder nicht, und was diese Trennzeichen sind - wenn überhaupt - ist auch nicht bekannt.

Bisher habe ich den folgenden Code in einem Versuch, geschrieben zu „lösen“ dies:

strings = [ 
    'cabhb2k4ack_sfdfd~ffrref_lk', 
    'iodja_24ed~092oi3jelk_fcjcad', 
    'lkn04432m_90osidjlknxc~o_pf' 
] 

# Process first line 
line1 = strings[0] 
separators = set() 
for sep in set(line1): 
    separators.add((sep, line1.count(sep))) 

# Process all the others 
for line in strings: 
    for sep,sepcount in separators.copy(): 
     if line.count(sep) != sepcount: separators.remove((sep,sepcount)) 

print separators 

Es gibt den Satz: set([('_', 2), ('~', 1)]) was gut ist - aber leider nicht die Reihenfolge der Separatoren in der enthält Datei. In der Tat ist es nicht einmal bekannt, ob es eine beständige Reihenfolge für diese Separatoren gab.

Die Regeln für die Separatoren sind einfach:

1. Sie die gleiche Anzahl, wie oft pro Zeile erfolgen muss,
2. Sie in der gleichen Reihenfolge auf jeder Zeile erfolgen muss,
3. Keiner der nicht Trennzeichen können Trennzeichen sein.

Beachten Sie, dass im obigen Beispiel, ‚4‘ als Trenn ausgeschlossen wurde, da es zweimal in der dritten Saite kommt für Grund 1 und 3

Die Frage
Wie kann ich ändern Dieser Code zum Überprüfen der Regel 2 druckt die Reihenfolge der Trennzeichen korrekt?

Answer 1

würde ich ein Counter statt .count, skrrgwasme Vorschlag, eine Liste zu verwenden nehmen, und verwenden Sie itertools.combinations Iterierte über die Untergruppen von möglichen Separatoren zu helfen:

from collections import Counter 
from itertools import combinations 

def subsets(elems): 
    for width in range(1, len(elems)+1): 
     for comb in combinations(elems, width): 
      yield comb 

def sep_order(string, chars): 
    chars = set(chars) 
    order = tuple(c for c in string if c in chars) 
    return order 

def find_viable_separators(strings): 
    counts = [Counter(s) for s in strings] 
    chars = {c for c in counts[0] 
      if all(count[c]==counts[0][c] for count in counts)} 
    for seps in subsets(chars): 
     orders = {sep_order(s, seps) for s in strings} 
     if len(orders) == 1: 
      yield seps, next(iter(orders)) 

die mich

>>> 
... strings = [ 
...  'cabhb2k4ack_sfdfd~ffrref_lk', 
...  'iodja_24ed~092oi3jelk_fcjcad', 
...  'lkn04432m_90osidjlknxc~o_pf' 
... ] 
... 
... for seps, order in find_viable_separators(strings): 
...  print("possible separators:", seps, "with order:", order) 
...    
possible separators: ('~',) with order: ('~',) 
possible separators: ('_',) with order: ('_', '_') 
possible separators: ('~', '_') with order: ('_', '~', '_') 

gibt

Answer 2

Bei der Regel 1 hat jedes Trennzeichen eine Anzahl von Vorkommen/Zeile, die von der ersten bis zur letzten Zeile der Liste stetig ist.

Ich finde die Regel 3 nicht sehr gut ausgedrückt. Ich denke, es muss verstanden werden als: "Jedes Zeichen, das als Trennzeichen verwendet wird, kann nicht gefunden werden, unter anderem Zeichen, die als Nicht-Trennzeichen in der Zeile betrachtet werden".

Mit den Regeln 1 UND 3 kann also jedes Zeichen, dessen Anzahl von Vorkommen/Zeile sich auch nur einmal zwischen zwei aufeinanderfolgenden Zeilen ändert, kein Trennzeichen sein.

also das Prinzip des Code unten ist
· zunächst eine Liste sep_n aller Zeichen in der ersten Zeile mit ihrer Anzahl von Vorkommnissen in dieser ersten Linie verbunden zu schaffen,
· und dann entlang iterieren die Liste der Zeilen S und jedes Zeichen in der Liste sep_n zu eliminieren, deren Anzahl der Vorkommen nicht gleich bleibt.

S = [ 
    'cabhb2k4ack_sfdfd~ffrref_lk', 
    'iodja_24ed~092oi3jelk_fcjcad', 
    'lkn04432m_90osidjlknxc~o_pf', 
    'hgtr5v_8mgojnb5+87rt~lhiuhfj_n547' 
    ] 
# 1.They must occur the same number of times per line, 
line0 = S.pop(0) 
sep_n = [ (c,line0.count(c)) for c in line0] 
print(line0); print(sep_n,'\n') 

for line in S: 
    sep_n = [x for x in sep_n if line.count(x[0]) == x[1]] 
    print(line); print(sep_n,'\n') 

S.insert(0, line0) 

# 2.They must occur in the same order on each line, 
separators_in_order = [x[0] for x in sep_n] 
print('separators_in_order : ',separators_in_order) 
separators   = ''.join(set(separators_in_order)) 

for i,line in enumerate(S): 
    if [c for c in line if c in separators] != separators_in_order: 
     print(i,line) 

Wenn die Zeichen in den Zeilen genug Variation ihrer Vorkommen haben (außer den Separatoren), die Länge der sep_n in meinen Code schnell abnimmt, wie die Liste iteriert wird.

.

Die Anweisung sep_n = [ (c,line0.count(c)) for c in line0] ist verantwortlich für die Tatsache, dass die endgültige Bestellung in separators_in_order erhalten ist die Reihenfolge in der ersten Zeile der Liste S.

Aber ich kann mir keinen Weg vorstellen zu testen, dass die Reihenfolge der Separatoren von einer Linie zur anderen gleich bleibt. Tatsächlich scheint es mir unmöglich, einen solchen Test während der Iteration durchzuführen, da die Liste der Separatoren erst vollständig bekannt ist, nachdem die Iteration vollständig durchgeführt wurde.

Deshalb muss eine sekundäre Kontrolle durchgeführt werden, nachdem der Wert sep_n erreicht wurde. Es muss erneut durch die Liste S iterieren.
Das Problem ist, dass wenn "jedes Zeichen, dessen Anzahl von Vorkommen/Zeile auch nur einmal zwischen zwei aufeinander folgenden Zeilen variiert, kein Trennzeichen sein kann", kann es vorkommen, dass ein Nicht-Trennzeichen streng erscheinen würde die gleiche Anzahl von Malen in allen Zeilen, also ohne die Möglichkeit, sie als Nicht-Trennzeichen auf der Grundlage der Anzahl von Vorkommen zu erkennen.
Da es jedoch eine Chance bleibt, dass ein solches Nicht-Trennzeichen nicht immer an der gleichen Stelle in der Liste von Zeichen mit stetigen Vorkommen platziert wird, ist die sekundäre Überprüfung möglich. Ein Extremfall, der existieren könnte, ist schließlich folgendes: Ein Nicht-Trennzeichen erscheint mit genau den gleichen Vorkommen in allen Zeilen und wird zwischen Trennzeichen in den Zeilen gesetzt, so dass es selbst durch nicht erkannt werden kann die sekundäre Überprüfung;
Ich weiß nicht, wie um diesen Fall zu lösen ....

Das Ergebnis ist

cabhb2k4ack_sfdfd~ffrref_lk 
[('c', 2), ('a', 2), ('b', 2), ('h', 1), ('b', 2), ('2', 1), ('k', 3), ('4', 1), ('a', 2), ('c', 2), ('k', 3), ('_', 2), ('s', 1), ('f', 5), ('d', 2), ('f', 5), ('d', 2), ('~', 1), ('f', 5), ('f', 5), ('r', 2), ('r', 2), ('e', 1), ('f', 5), ('_', 2), ('l', 1), ('k', 3)] 

iodja_24ed~092oi3jelk_fcjcad 
[('c', 2), ('a', 2), ('4', 1), ('a', 2), ('c', 2), ('_', 2), ('~', 1), ('_', 2), ('l', 1)] 

lkn04432m_90osidjlknxc~o_pf 
[('_', 2), ('~', 1), ('_', 2)] 

hgtr5v_8mgojnb5+87rt~lhiuhfj_n547 
[('_', 2), ('~', 1), ('_', 2)] 

separators_in_order : ['_', '~', '_'] 

Und mit

S = [ 
    'cabhb2k4ack_sfd#fd~ffrref_lk', 
    'iodja_24ed~092oi#3jelk_fcjcad', 
    'lkn04432m_90osi#djlknxc~o_pf', 
    'h#gtr5v_8mgojnb5+87rt~lhiuhfj_n547' 
    ] 

das Ergebnis ist

cabhb2k4ack_sfd#fd~ffrref_lk 
[('c', 2), ('a', 2), ('b', 2), ('h', 1), ('b', 2), ('2', 1), ('k', 3), ('4', 1), ('a', 2), ('c', 2), ('k', 3), ('_', 2), ('s', 1), ('f', 5), ('d', 2), ('#', 1), ('f', 5), ('d', 2), ('~', 1), ('f', 5), ('f', 5), ('r', 2), ('r', 2), ('e', 1), ('f', 5), ('_', 2), ('l', 1), ('k', 3)] 

iodja_24ed~092oi#3jelk_fcjcad 
[('c', 2), ('a', 2), ('4', 1), ('a', 2), ('c', 2), ('_', 2), ('#', 1), ('~', 1), ('_', 2), ('l', 1)] 

lkn04432m_90osi#djlknxc~o_pf 
[('_', 2), ('#', 1), ('~', 1), ('_', 2)] 

h#gtr5v_8mgojnb5+87rt~lhiuhfj_n547 
[('_', 2), ('#', 1), ('~', 1), ('_', 2)] 

separators_in_order : ['_', '#', '~', '_'] 
1 iodja_24ed~092oi#3jelk_fcjcad 
3 h#gtr5v_8mgojnb5+87rt~lhiuhfj_n547 

.
.

NB 1
Die Anweisung line0 = S.pop(0) erfolgt
eine Anweisung for line in S[1:]: off zur Daube,
weil S[1:] eine neue Liste erstellt, die schwer sein könnte.

.

NB 2
Um die Schaffung einer neuen sep_n Liste bei jeder Umdrehung der Iteration in S,
es besser zu vermeiden, ist die Iteration zu schreiben, wie folgt:

for line in S: 
    for x in sep_n: 
     if line.count(x[0]) == x[1]: 
      sep_n = [x for x in sep_n if line.count(x[0]) == x[1]] 
      break 
    print(line); print(sep_n,'\n')