Discussion :

[Amybond]

Bonjour,
Je souhaite répertorier toutes les séquences répétées (de longueurs variables) dans un texte donné pour créer un décrypteur du chiffre de Vigenère.
Donc ce sont des séquences quelconques. http://www.apprendre-en-ligne.net/cr...decodevig.html. Comment dois-je m'y prendre ?

Merci d'avance

[Obsidian]

Bonjour,

Sinon, sur le fond, sans être un expert, je pense que la compression de Huffmann se rapproche de ce que tu veux faire (fais une recherche ici).

[Jean-Marc.Bourguet]

Sinon, sur le fond, sans être un expert, je pense que la compression de Huffmann se rapproche de ce que tu veux faire (fais une recherche ici).

Je ne vois pas en quoi la compression de Huffmann se rapproche de la determination de sequences repetees.

Je trierais simplement les sous-chaines s'etendant jusqu'a la fin, c'est alors facile de trouver les repetitions d'une longueur minimale (les repetitions se suivent apres le tri).

[pseudocode]

Je vois bien une grosse matrice de co-occurence des lettres...

Une matrice 26*26 avec en colonne "a,b,c,...,z" et pareil pour les lignes.
Tu parcours le texte lettre par lettre et tu incrémentes la case[i,j] a chaque fois que la lettre 'i' est suivie de la lettre 'j'.

Ensuite on peut reconstruire les "chemins" en utilisant cette matrice comme une matrice d'adjacence de graphe orienté.

[Jean-Marc.Bourguet]

Je vois bien une grosse matrice de co-occurence des lettres...

Une matrice 26*26 avec en colonne "a,b,c,...,z" et pareil pour les lignes.
Tu parcours le texte lettre par lettre et tu incrémentes la case[i,j] a chaque fois que la lettre 'i' est suivie de la lettre 'j'.

Ensuite on peut reconstruire les "chemins" en utilisant cette matrice comme une matrice d'adjacence de graphe orienté.

J'ai du mal a voir comment s'en servir pour reperer les repetitions. Ma proposition est proche de la transformation de Burrozs-Wheeler, simplement je ne prends pas des rotations mais les sous-chaines, et apres le tri on a les repetitions qui sont groupees.

[Amybond]

Merci pour vos réponses

Je trierais simplement les sous-chaines s'etendant jusqu'a la fin, c'est alors facile de trouver les repetitions d'une longueur minimale (les repetitions se suivent apres le tri).

Des sous-chaines de combien de caractères ?

[Jean-Marc.Bourguet]

Merci pour vos réponses




Des sous-chaines de combien de caractères ?

Jusqu'à la fin du texte. Tu peux éviter de dupliquer l'info en les représentant par des pointeurs vers l'endroit adéquat dans le texte, ou des indices dans un tableau.

[pseudocode]

J'ai du mal a voir comment s'en servir pour reperer les repetitions.

exemple: ABCAABCBABC

Code :

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

1
2
3
4
5
6
 
  @ A B C
@        
A   1 3  
B   1   3
C   1 1

liste des séquences de 2 lettres avec une occurrence > 1:
AB(x3)
BC(x3)

liste des séquences de 3 lettres = séquences de 2 lettres + 1 lettre
AB(x3) + BC(x3) = ABC(x3)
AB(x3) + BA(x1) = ABA(x1) 1 seule occurrence -> ignore
BC(x3) + CA(x1) = BCA(x1) 1 seule occurrence -> ignore
BC(x3) + CB(x1) = BCA(x1) 1 seule occurrence -> ignore

liste des séquences de 4 lettres = séquences de 3 lettres + 1 lettre
ABC(x3) + CA(x1) = ABCA(x1) 1 seule occurrence -> ignore
ABC(x3) + CB(x1) = ABCB(x1) 1 seule occurrence -> ignore

FIN

[Amybond]

Ok merci je vais essayer d'implémenter cela.
Je vous tiens au courant

[Jean-Marc.Bourguet]

Pseudocode sur ABXABXBCXBC tu vas avoir un faux positif pour ABC.

Je suis en veine de bonté:

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
#include <iostream>
#include <ostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <set>
 
struct Sequence
{
    Sequence(char const* pPos, size_t pLength) : pos(pPos), length(pLength) {}
 
    char const* pos;
    size_t length;
};
 
size_t commonPrefixSize(char const* s1, char const* s2)
{
    size_t result = 0;
    while (*s1 != '\0' && *s1 == *s2) {
        ++s1;
        ++s2;
        ++result;
    }
    return result;
}
 
std::ostream& operator<<(std::ostream& os, Sequence const& s)
{
    os.write(s.pos, s.length);
}
 
bool isLonger(Sequence const& l, Sequence const& r)
{
    return l.length > r.length;
}
 
struct SequenceSetLess
{
    bool operator() (Sequence const& l, Sequence const& r)
    {
        int s = strncmp(l.pos, r.pos, std::min(l.length, r.length));
        return (s < 0) || (s == 0 && l.length < r.length);
    }
};
 
bool isBefore(char const* l, char const* r)
{
    return strcmp(l, r) < 0;
}
 
void showRepeatedSequences(std::ostream& os, char const* s)
{
    std::vector<char const*> substrings;
    for (; *s != '\0'; ++s) {
        substrings.push_back(s);
    }
 
    sort(substrings.begin(), substrings.end(), isBefore);
 
    std::set<Sequence, SequenceSetLess> sequences;
    for (std::vector<char const*>::iterator i = substrings.begin();
         i+1 != substrings.end();
         ++i)
    {
        size_t prefixSize = commonPrefixSize(*i, *(i+1));
        if (prefixSize > 0) {
            sequences.insert(Sequence(*i, prefixSize));
        }
    }
 
    std::vector<Sequence> seqTable(sequences.begin(), sequences.end());
 
    sort(seqTable.begin(), seqTable.end(), isLonger);
 
    std::copy(seqTable.begin(), seqTable.end(),
              std::ostream_iterator<Sequence>(os, "\n"));
}
 
int main(int argc, char* argv[])
{
    for (++argv; *argv != NULL; ++argv) {
        std::cout << "\n" << *argv << " repeated substrings:\n";
        showRepeatedSequences(std::cout, *argv);
    }
}