Discussion :

[bizet]

Bonjour,

dans le cadre d'un projet OCR, je dois comparer deux string extraites de pages différentes pour retrouver la même zone de texte.

Or je rencontre quelques problèmes dans l'algo permettant de comparer mes strings.

Pour le moment j'ai trouvé un script sur le net qui met mes deux chaines dans un tableau contenant le caractère et l'indice dans la string.
Puis je classe cette string par ordre alphabétique avant de comparer caractère par caractère d'où j'extrais un nombre a ajouter ou a soustraire que selon la comparaison.

Le code : (Désolé c'est du VB.net)

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
longStr = Math.Max(chaine1.Length, chaine2.Length)
 
            'Si une des chaines est vide, on considere qu'il n'y a pas de concordance
            If (String.IsNullOrEmpty(chaine1) Or String.IsNullOrEmpty(chaine2)) Then
                Return 0
            End If
 
            Dim ind As Integer = 0
            Dim tailleA As Integer = 0
            Dim tailleB As Integer = 0
            For indexA = 1 To longStr
                If chaine1.Length >= indexA Then
                    tailleA += 1
                    PatternA(ind).tableau = New Byte(1) {}
 
                    PatternA(ind).tableau(0) = Convert.ToByte(chaine1(indexA - 1))
                    PatternA(ind).tableau(1) = Convert.ToByte(indexA - 1)
                End If
                If chaine2.Length >= indexA Then
                    tailleB += 1
                    PatternB(ind).tableau = New Byte(1) {}
                    PatternB(ind).tableau(0) = Convert.ToByte(chaine2(indexA - 1))
                    PatternB(ind).tableau(1) = Convert.ToByte(indexA - 1)
                End If
                ind += 1
            Next
 
            indexA = 0
            indexB = 0
 
            While (indexA < (tailleA - 1)) AndAlso (indexB < (tailleB - 1))
                If tailleA > indexA Then
                    If PatternA(indexA).tableau(0) < PatternA(indexA + 1).tableau(0) Then
                        tpmPattern.tableau(0) = PatternA(indexA).tableau(0)
                        tpmPattern.tableau(1) = PatternA(indexA).tableau(1)
                        PatternA(indexA).tableau(0) = PatternA(indexA + 1).tableau(0)
                        PatternA(indexA).tableau(1) = PatternA(indexA + 1).tableau(1)
                        PatternA(indexA + 1).tableau(0) = tpmPattern.tableau(0)
                        PatternA(indexA + 1).tableau(1) = tpmPattern.tableau(1)
 
                        If indexA > 0 Then
                            indexA -= 1
                        End If
                    Else
                        indexA += 1
                    End If
                End If
                If tailleB > indexB Then
 
                    If PatternB(indexB).tableau(0) < PatternB(indexB + 1).tableau(0) Then
                        tpmPattern.tableau(0) = PatternB(indexB).tableau(0)
                        tpmPattern.tableau(1) = PatternB(indexB).tableau(1)
                        PatternB(indexB).tableau(0) = PatternB(indexB + 1).tableau(0)
                        PatternB(indexB).tableau(1) = PatternB(indexB + 1).tableau(1)
                        PatternB(indexB + 1).tableau(0) = tpmPattern.tableau(0)
                        PatternB(indexB + 1).tableau(1) = tpmPattern.tableau(1)
 
                        If indexB > 0 Then
                            indexB -= 1
 
                        End If
                    Else
                        indexB += 1
                    End If
                End If
            End While
            ' Calculating simularity percentage
            longStr = Math.Min(tailleA, tailleB)
            For indexA = 0 To (longStr - 1)
                If PatternA(indexA).tableau(0) = PatternB(indexA).tableau(0) Then
                    Dim tp2 As Byte = Math.Min(PatternA(indexA).tableau(1), PatternB(indexA).tableau(1))
                    Dim tp1 As Byte = Math.Max(PatternA(indexA).tableau(1), PatternB(indexA).tableau(1))
 
                    If (tp1 - tp2) > 0 Then
 
                        Dim nombre As Decimal = (100 / longStr) / (Math.Max(PatternA(indexA).tableau(1), PatternB(indexA).tableau(1)) - Math.Min(PatternA(indexA).tableau(1), PatternB(indexA).tableau(1)))
                        result = result - (Convert.ToInt32(nombre))
                    Else
                        If result < 100 Then
                            result += (Convert.ToInt32(100 / longStr))
                        End If
                    End If
                Else
                    result = result - (Convert.ToInt32(100 / longStr))
                End If
            Next

Le probleme est que cela retourne des résultats pas assez précis :

exemple :
TEST -- Attendu : EDFPOURLESENTREPRISES -- Trouve : EDFPOURLESEMREPRNSES -- Correspondance : 57%

TEST -- Attendu : EDFPOURLESENTREPRISES -- Trouve : EDFPOURLESEMREPRISES -- Correspondance : 58%

TEST -- Attendu : EDFPOURLESENTREPRISES -- Trouve : EDFPOURLASENTRSPRISES -- Correspondance : 53%

TEST -- Attendu : TOTALFACTURE -- Trouve : TOTALFACTURS -- Correspondance : <80%

J'ai remarqué sur ce dernier exemple que le E va etre dans les premieres cases une fois classée par ordre alphabétique et va donc décaler l'ensemble de la comparaison, d'ou un pourcentage trop faible.

Auriez vous quelques solutions/idées pour améliorer le pourcentage retourné?

Est ce que je devrais supprimer ce tri par ordre alphabétique? Le probleme de cette solution est que l'ajout d'un caractère va decaler toutes mes comparaisons...

Merci de vos suggestions.

[ArgusAzure]

A toi de définir ta propre mesure de distance entre 2 chaines. Pourquoi ne pas considérer les espaces, c'est un choix délibéré?
Tu peux faire un truc du style : considérer les groupes de 3 lettres. Rechercher la presence de chaque groupe dans l'autre chaine dans le voisinage de l'endroit où tu es censé le trouver.
Je sais pas si c'est très clair...
Pourquoi un groupe de 3 lettres et non des lettres individuelles, bonne question

[bizet]

A toi de définir ta propre mesure de distance entre 2 chaines. Pourquoi ne pas considérer les espaces, c'est un choix délibéré?
Tu peux faire un truc du style : considérer les groupes de 3 lettres. Rechercher la presence de chaque groupe dans l'autre chaine dans le voisinage de l'endroit où tu es censé le trouver.
Je sais pas si c'est très clair...
Pourquoi un groupe de 3 lettres et non des lettres individuelles, bonne question

C'est un choix délibéré d'enlever les caractères, comme tous les caractères spéciaux '(-`_,...
En effet la reconnaissance de caractère en rajoute pas mal entre les lettres.

Ta solution de 3 lettres n'est pas satisfaisante car le probleme des reconnaissances de caractères est qu'il y a souvent inversion de lettres (a->e) (n->m) or si j'ai cette inversion dans un groupe, je suis sur de ne pas le trouver et de plomber mes pourcentages.

Mais merci de ton aide

[Jean-Marc.Bourguet]

Pourquoi ne pas utiliser un algo plus connu comme la Distance de Levenshtein? Tu peux meme diminuer le cout des permutations probables.

[bizet]

Pourquoi ne pas utiliser un algo plus connu comme la Distance de Levenshtein? Tu peux meme diminuer le cout des permutations probables.

Tout simplement parce que je ne connaissais pas cette distance de Levenshtein malgré toutes mes recherches sur le net je n'etais jamais tombé là dessus.

Merci J-M Bourguet, je vais implémenter cette solution qui me parait la plus adéquate la tester et je vous tiendrais au courant

[bizet]

Tout est bon et ca correspond pas trop mal a ce que je veux.

Merci