Contig? String aus Teilst. zusammensetzen?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
RedSharky
User
Beiträge: 99
Registriert: Donnerstag 13. April 2006, 15:38

Montag 27. Oktober 2008, 16:06

Hi!

Ich suche eine Möglichkeit aus mehreren Teilstücken den kompletten String zusammenzusetzen.

Etwa so:

Dies ist ein langer St
n langer String, der aus mehreren Einzel
reren Einzelteilen zusammengesetzt wurde.

=>

Dies ist ein langer String, der aus mehreren Einzelteilen zusammengesetzt wurde.



Ich kenne etwas ähnliches aus der Molekularbiologie. Dort benutzt man sogenannte Contig-Programme, um sich aus Sequenzbruchstücken die komplette Sequenz zusammen zu puzzeln. Jedoch sind diese Programme meist nur auf die Zeichen ATGC beschränkt und haben zusätzliche Funktionen, um fehlertoleranter zu sein (in meinem Fall absoluter Overkill).

Was ich versuche ist eher den Text aus einem Newsticker zusammenzusetzen.

Gibt es eine solche Funktion z. B. in den Standardmodulen oder muss ich mir sowas selbst schreiben? Oder hat jemand eine Idee, wie sowas möglichst einfach zu machen wäre?
Lonestar
User
Beiträge: 147
Registriert: Samstag 9. August 2008, 08:31

Montag 27. Oktober 2008, 16:15

du meinst nicht zufällig sowas, oder?

Code: Alles auswählen

>>> a = "Dies ist ein langer String"
>>> b = ", der aus mehreren "
>>> c = "Einzelteilen zusammengesetzt wurde. "
>>> d = a + b + c
>>> print d
Dies ist ein langer String, der aus mehreren Einzelteilen zusammengesetzt wurde. 
>>> 
RedSharky
User
Beiträge: 99
Registriert: Donnerstag 13. April 2006, 15:38

Montag 27. Oktober 2008, 16:19

Es geht darum, dass die sich überlappenden Teilstrings zusammengesetzt werden sollen (siehe Beispiel oben).


---

Edit:

Ich hoffe, aus diesem Beispiel geht das deutlicher hervor:

Code: Alles auswählen

SUB1:	Dies ist ein langer St
SUB2:	n langer String, der aus mehreren Einzel
SUB3:	reren Einzelteilen zusammengesetzt wurde.

SUB1:	Dies ist ein langer St----------------------------------------------------------
SUB2:	-----------n langer String, der aus mehreren Einzel-----------------------------
SUB3:	---------------------------------------reren Einzelteilen zusammengesetzt wurde.
CONTIG:  Dies ist ein langer String, der aus mehreren Einzelteilen zusammengesetzt wurde.
Zuletzt geändert von RedSharky am Montag 27. Oktober 2008, 16:26, insgesamt 1-mal geändert.
Lonestar
User
Beiträge: 147
Registriert: Samstag 9. August 2008, 08:31

Montag 27. Oktober 2008, 16:25

ok, das hört sich schon aufwendiger an. An diesem Punkt gebe ich mal weiter :roll:
n4p
User
Beiträge: 55
Registriert: Dienstag 10. Juni 2008, 11:05

Montag 27. Oktober 2008, 16:40

Code: Alles auswählen

lst = ('Dies ist ein langer St','n langer String, der aus mehreren Einzel','reren Einzelteilen zusammengesetzt wurde.')

ausgabe, ende = '', ''

def stueckl(ende, zeile):
    return zeile[zeile.find(ende):-5]


for s in lst:
    ausgabe += stueckl(ende, s)
    ende = s[-5:]

ausgabe += lst[len(lst)-1][-5:]
print ausgabe
Als Grundlage zum weiterbasteln, zerfetzen und auslachen :)
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Montag 27. Oktober 2008, 17:34

Code: Alles auswählen

parts = ['Dies ist ein langer St',
        'n langer String, der aus mehreren Einzel',
        'reren Einzelteilen zusammengesetzt wurde.']

for n in xrange(1,len(parts)):
    for k in xrange(len(parts[n]),0,-1):
        if parts[n-1].endswith(parts[n][:k]):
            parts[n] = parts[n-1]+parts[n][k:]
            break
            
print parts[-1]
Liefert:

Code: Alles auswählen

Dies ist ein langer String, der aus mehreren Einzelteilen zusammengesetzt wurde.
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

Montag 27. Oktober 2008, 17:46

Oder so:

Code: Alles auswählen

def contig(a, b):
    for i in xrange(min(len(a), len(b))):
        if a[-i:] == b[:i]: return a[:-i] + b
    else: return a + b

s = [
    'Dies ist ein langer St',
    'n langer String, der aus mehreren Einzel',
    'reren Einzelteilen zusammengesetzt wurde.'
]
print reduce(contig, s)
PS: Hätte ich von endswith gewusst, wärs vermutlich sogar schöner gelungen ;)
RedSharky
User
Beiträge: 99
Registriert: Donnerstag 13. April 2006, 15:38

Montag 27. Oktober 2008, 20:40

Ich hatte ja eigentlich gehofft, dass da irgend eine mir unbekannte Funktion in einem Standardmodul helfen könnte. Die scheint es aber wohl nicht zu geben.

Eure Ideen sind aber sehr vielversprechend.
Ich danke euch!
RedSharky
User
Beiträge: 99
Registriert: Donnerstag 13. April 2006, 15:38

Dienstag 28. Oktober 2008, 09:06

So, ich hab mal was zusammengebastelt, um das Ganze etwas flexibler zu machen.

Das Ergebnis bis hierhin:

Code: Alles auswählen

OVERLAP = 8
skip = []

s = [
    'ammengesetzt wurd',
    'n Einzelteilen', 
    'nger String, der aus m',
    'n langer String, der aus mehreren Einzel',
    'Dies ist ein langer St',
    'reren Einzelteilen zusammengesetzt wurde.',
    'langer String,'
]


def contig(a,b):
    if a.find(b) != -1:     #if b is just a substring of a
        return a
    elif b.find(a) != -1:   #if a is just a substring of b
        return b
    else:
        for i in xrange(OVERLAP,min(len(a), len(b))):
            if b.startswith(a[-i:]):
                return a[:-i] + b
            elif a.startswith(b[-i:]):
                return b[:-i] + a
        else:
            skip.append(a)
            return b


precont = reduce(contig, s)
skip.insert(0,precont)  #considering skipped items

print reduce(contig, skip)
Antworten