Эффективный сдвиг инвариантна функция преобразования текста

Question

Edit

Есть 3 непрерывные битовые. Когда-то они начинают читать их. Через некоторое время одна остановка и имеет теперь 3 очень длинные строки одинаковой длины.

Эти 3 строки должны содержать отправленное сообщение где-то посередине. За исключением сообщений, отправляемых случайными битами.

Теперь задача состоит в том, чтобы выяснить, как наложить 3 строки для дальнейшей коррекции ошибок.

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

вот простой пример. Теперь то, что я хочу это

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

теперь я могу просто использовать большинство голосов и получить правильную последовательность

<<this is a string>> 

Как бы достичь этого эффективно?

Answer 1

Исследовательское программирование в TXR LISP:

Содержание 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))) 

Интерактивная сессия:

$ 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>>"