changement efficace de fonction invariante pour transformer le texte

Question

Modifier

Il y a 3 continu des flux binaires. À un moment on commence à les lire. Après un certain temps on s'arrête et a maintenant 3 très longues cordes de la même longueur.

Ces 3 chaînes doivent contenir le message envoyé quelque part entre les deux. Sauf pour le message, des bits aléatoires sont envoyés.

L'objectif serait maintenant, pour savoir comment superposer les 3 chaînes pour effectuer une correction d'erreur.

hfkasjkfhjs<<this is a string><hjaksdf 
jkdf::this is b strimg>>iowefjlasfjoie 
jfaskflsjdflf<<this is a tring>>oweio 

Voici un exemple simple. Maintenant, ce que je veux est ce

<<this is a string>< 
::this is b string>> 
<<this is a tring>> 

maintenant je peux utiliser le vote à la majorité et obtenir la séquence correcte

<<this is a string>> 

Comment puis-je parvenir efficacement?

Answer 1

programmation exploratoire TXR Lisp:

Contenu de fuzz-extract.tl:

(defun fuzz (str) 
    (window-map 1 " " 
       (do if (memql #\X @rest) 
       #\X #\space) 
       str)) 

(defun correlate (str1 str2 thresh) 
    (let ((len (length str1)) 
     (pat (mkstring thresh #\X))) 
    (each ((offs (range* 0 len))) 
     (let* ((str2-shf `@[str2 offs..:]@[str2 0..offs]`) 
      (str2-dshf `@{str2-shf}@{str2-shf}`) 
      (raw-diff (mapcar [iff eql (ret #\X) (ret #\space)] 
           str1 str2-dshf)) 
      (diff (fuzz raw-diff)) 
      (pos (search-str diff pat))) 
     (if pos 
      (let ((rng (+ (r^ #/X+/ pos diff) #R(-2 2)))) 
      (if (< (from rng) 0) 
       (set rng 0..(to rng))) 
      (return-from correlate [str1 rng]))))))) 

(defun count-same (big-s lit-s offs) 
    (countq t [mapcar eql [big-s offs..:] lit-s])) 

(defun find-off (big-s lit-s) 
    (let ((idx-count-pairs (collect-each ((i (range 0 (- (length big-s) 
                 (length lit-s))))) 
          (list i (count-same big-s lit-s i))))) 
    (first [find-max idx-count-pairs : second]))) 

(defun extract-from-three (str1 str2 str3 : (thresh 10)) 
    (let* ((ss1 (correlate str1 str2 thresh)) 
     (ss2 (correlate str2 str3 thresh)) 
     (ss3 (correlate str3 str1 thresh)) 
     (maxlen [[mapf max length length length] ss1 ss2 ss3]) 
     (pad (mkstring (trunc maxlen 2) #\space)) 
     (buf1 `@pad@ss1@pad`) 
     (off1 (find-off buf1 ss2)) 
     (buf2 `@{"" off1}@ss2`) 
     (off2 (find-off buf1 ss3)) 
     (buf3 `@{"" off2}@ss3`)) 
    (mapcar (do cond 
       ((eql @1 @2) @1) 
       ((eql @2 @3) @2) 
       ((eql @3 @1) @3) 
       (t #\space)) 
      buf1 buf2 buf3))) 

session interactive:

$ txr -i fuzz-extract.tl 
1> (extract-from-three 
    "hfkasjkfhjs<<this is a string><hjaksdf" 
    "jkdf::this is b strimg>>iowefjlasfjoie" 
    "jfaskflsjdflf<<this is a tring>>oweio") 
"    f<<this is a string>> " 
2> (trim-str *1) 
"f<<this is a string>>"