Contig? String aus Teilst. zusammensetzen?

[RedSharky]

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]

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]

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.

[Lonestar]

ok, das hört sich schon aufwendiger an. An diesem Punkt gebe ich mal weiter

[n4p]

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

[numerix]

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]

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]

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]

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)