Discussion :

[N.tox]

Salut,

Je me retrouve devant un problème que je sais résoudre humainement, mais pas "mécaniquement"...

j'ai deux textes A et B, dans un premier temps, je repère tous les passages communs, ça c'est fait, y'a pas de problème, j'obtiens une liste de tuples, où chaque tuple est composé de trois éléments :
(index de début dans A, index de fin dans A) , (index de début dans B, index de fin dans B) , "texte en commun"

concrètement, pour les deux textes suivants :
'fouimnqdononmlie' et 'kjdiouifjlsdnon'
j'obtiens la liste de tuple suivants:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
( 9, 12), (12, 15), 'non'
( 1,  4), ( 4,  7), 'oui'
(14, 15), ( 3,  4), 'i'
(13, 14), ( 9, 10), 'l'
( 7,  8), ( 2,  3), 'd'
( 0,  1), ( 7,  8), 'f'

J'aimerais maintenant travailler ces données de façon à obtenir ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
( 1,  4), ( 4,  7), 'oui'
( 7,  8), ( 2,  3), 'd'
( 9, 12), (12, 15), 'non'

'oui' est bien avant 'd' dans les deux textes, et 'd' avant 'non' dans les deux textes. Je ne sais pas pourquoi, mais je n'arrive pas à établir la logique algorythmique me permettant d'obtenir ce résultat depuis les données précédements obtenues...
Quelqu'un pourrait-il m'orienter ?

[ju_bicycle]

J'ai p'tet pas tout compris, mais il me semble que "d" n'est pas forcément toujours avant d
exemple:
'kjdiouifjlsdnon"

(En fait tu as 2 "d" alors y'en a un devant et un derriere)
Ce qui donne des indexs qui ne sont pas dans l'ordre croissant forcément...

Par contre, une fois que tu n'a plus ce probleme de doublon, il devient facile de trier tes tuples par simple ordre croissant des indexs non?

[tyrtamos]

Bonjour,

Si j'ai bien compris, tu veux ranger dans l'ordre croissant des début des chaines dans le texte A.

Il y a une solution simple: si ça figure dans une liste, il suffit de trier! Pour cela, il faut construire la liste suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
L = [[[ 9, 12], [12, 15], 'non'],
[[ 1,  4], [ 4,  7], 'oui'],
[[14, 15], [ 3,  4], 'i'],
[[13, 14], [ 9, 10], 'l'],
[[ 7,  8], [2,  3], 'd'],
[[ 0,  1], [ 7,  8], 'f']]

Puis, on la trie:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

L.sort()

Ce qui donne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
for x in L:
    print x
 
[[0, 1], [7, 8], 'f']
[[1, 4], [4, 7], 'oui']
[[7, 8], [2, 3], 'd']
[[9, 12], [12, 15], 'non']
[[13, 14], [9, 10], 'l']
[[14, 15], [3, 4], 'i']

Avec la méthode sort() (ou la fonction sorted), on peut faire des tris plus complexes en ajoutant des fonctions de comparaison et de conversion comme paramètres.

Tyrtamos

[N.tox]

Mersi pour vos réponses.

Je connaissais déjà sort(), mais par exemple 'i' est après 'non' dans le texte A, mais pas avant 'non' dans le texte B, cet élément ne respecte donc pas la même chronologie dans les deux textes, et ne devrait pas se trouver dans le résultat... et il est bien là mon problème : trouver les éléments qui respectent la même chronologie dans les deux textes, et uniquement ceux-là

J'ai p'tet pas tout compris, mais il me semble que "d" n'est pas forcément toujours avant d
exemple:
'kjdiouifjlsdnon"

(En fait tu as 2 "d" alors y'en a un devant et un derriere)
Ce qui donne des indexs qui ne sont pas dans l'ordre croissant forcément...

il n'y a pas à s'en faire pour les doublons, je ne vais pas rentrer dans les détails, mais y'a pas à s'en faire pour ça (au pire je rebosserait ça dans mon coin plus tard)

[DelphiManiac]

et il est bien là mon problème : trouver les éléments qui respectent la même chronologie dans les deux textes, et uniquement ceux-là

D'un autre coté d est après oui dans A et avant oui dans B, il ne respecte pas non plus la même chronologie, et pourtant tu le fais apparaitre dans le résultat.

En gros, j'ai pas tout compris ^^

[edit]Après une toute petite recherche chez notre ami google, j'ai trouvé un lib python fourni de base qui permets de faire un diff:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
# usr/bin/env python
# -*- coding: utf-8 -*-
 
from difflib import ndiff
 
a = 'fouimnqdononmlie'
b = 'kjdiouifjlsdnon'
for l in ndiff(a, b):
    print l

Résultat :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
- f
+ k
+ j
+ d
+ i
  o
  u
  i
- m
- n
- q
+ f
+ j
+ l
+ s
  d
- o
  n
  o
  n
- m
- l
- i
- e

Cela semble correspondre à ce que tu cherches.

Voir http://docs.python.org/library/difflib.html pour de plus amples informations.

[N.tox]

excellent !
Merci beaucoup !

Pour 'd', oui, c'est vrai y'a une couille dans le paté, (j'ai humainement foiré la prévision du bon résultat au vu des données ennoncées )

edit : d'ailleurs, y'avais une couille dans mon algorythm de prélevement des données communes aux deux textes, ce qui est corrigé.
avec ndiff, c'est carrément trop simple ! Résolu !

[N.tox]

Mon but était de comparer deux fichiers "binaires" (mais pas des applications, donc heu... fichiers hex ?), et d'en relever autant les différence que les données communes.
voici le script que j'ai fini par pondre (pour ceux que ça intéresseraient):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
'''Compare two hex files and output any different or common parts
in a formated form'''
import sys
import difflib as dl
 
def cmpr(a,b):
    '''
    compare two strings, and yield any differnt or common parts in
    a tuple where first element is a character indicating the
    source ( 'A' : text a, 'B' : text b, 'C' common), and second
    element is the part of text'''
    def _yield():
        if   last == '  ': return ('C',tampon)
        elif last == '+ ': return ('B',tampon)
        elif last == '- ': return ('A',tampon)
    tampon  = last = ''
    diff    = dl.ndiff(a,b)
    while True:
        try: char = diff.next()
        except StopIteration:
            yield _yield()
            raise StopIteration
        if not last: last = char[:2]
        if char[:2] == last: tampon += char[2:]
        else:
            yield _yield()
            tampon  = char[2:]
            last    = char[:2]
 
def convert(txt):
    '''
    convert hex values of each character into readable text
    ex:
    '\\x00\\xf2' --> '00 F2' '''
    res = ''
    for x in txt:
        res += hex(ord(x))[2:].zfill(2).upper()+' '
    return res[:-1]
 
def format(mrg , txt, l=47):
    '''format the text to the mrg + (part of txt equal to l) per line'''
    mrg += ' : '
    lt   = len(txt)
    nd   = lt/l+(1 if lt%l else 0)
    return '\n'.join([mrg+txt[z*l+z:(z+1)*l+z] for z in xrange(nd)])
 
def getDiff(a,b):
    '''
    steam of all precedent functions:
    compare and yield formated converted text'''
    for x,y in cmpr(a,b):
        yield format(x, convert(y))
 
if __name__=='main':
    f_a,f_b = open(sys.argv[1],'r'),open(sys.argv[2],'r')
    a,b     = f_a.read(), f_b.read()
    f_a.close() ; f_b.close()
    del f_a,f_b
    for x in getDiff(a,b):
        print x
        print

on l'utilise (normalement) depuis le shell de la façon suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

compareHexFiles.py a b > comparison.txt

'comparison.txt' qui donne pour les deux fichiers que je voulais comparer :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
A : 02 AB 06 7C D6
 
B : DB 3B C9 54 25 C0 7D AE
 
C : 37
 
B : E8 5C 38 6F 68 42 2C 19 B5 46 82
 
A : 4E 3C BD 4A 36 C2 1B EB 27 C4 D1 8D DE 08
 
C : 00 00 01 2D 06 00 00 00 1B 01 00 00 00 02 70 00
C : 04 00 00 02 00 00 00 10 69 01 01 89 01 66 69 01
C : 06 89 01 67 69 01 04 89 01 68 68 01 A1 04 65 69
C : 01 0C 96 02 69 04 4C 07 A5 08 6A 28 29 00 6B 61
C : 04 08 81 04 6C 69 01 0A 89 01 6D 68 01 A5 08 6E
C : 28 29 00 6F
 
B : 28 29 00
 
A : 68 01 A5 08
 
C : 70 69 01 07 8D 05 71 68 01