Odnajdywanie pikseli, które sprawiają, że obraz jest unikalny na liście, można poprawić na brutalnej sile?

Question

Załóżmy, że mam listy ciągów znaków, gdzie każdy łańcuch jest

• dokładnie długości 4 znaków i
• unikalna w obrębie listy.

Dla każdego z tych napisów chcę zidentyfikować pozycję znaków w ciągu znaków, które powodują, że ciąg jest niepowtarzalny.

Więc do listy trzech ciągów

abcd 
abcc 
bbcb 

dla pierwszego łańcucha Chcę określić charakter w 4 pozycji d od d nie pojawiają się na 4 pozycji w inny ciąg.

Dla drugiego ciągu chcę zidentyfikować znak na 4. pozycji c.

Na trzecim ciągiem go Chcę określić charakter w 1. pozycji b i charakteru w 4 pozycji, także b.

To może być zwięźle przedstawiony jako

abcd -> ...d 
abcc -> ...c 
bbcb -> b..b 

Jeśli wziąć pod uwagę ten sam problem, ale z listą liczb binarnych

0101 
0011 
1111 

Następnie wynik chcę byłoby

0101 -> ..0. 
0011 -> .0.. 
1111 -> 1... 

Pozostając z motywem binarnym mogę użyć XOR, aby zidentyfikować, które bity są unikatowe w ramach dwa binarne numery od

0101^0011 = 0110 

które można interpretować w ten sposób, że w tym przypadku 2 i 3 bity (czytanie od lewej do prawej) są unikalne między tymi dwoma liczb binarnych. Ta technika może być czerwonym śledziem, chyba że w jakiś sposób może zostać rozszerzona na większą listę.

Metoda brute-force polegałaby na analizie każdego ciągu po kolei, a dla każdego ciągu na iterację pionowych wycinków pozostałych łańcuchów na liście.

Tak na liście

abcd 
abcc 
bbcb 

chciałbym zacząć

abcd 

i iterację pionowe plastry

abcc 
bbcb 

gdzie te pionowe plastry byłoby

a | b | c | c 
b | b | c | b 

lub w formie listy, "ab", "bb", "cc", "cb".

Spowodowałoby czterech porównaniach

a : ab -> . (a is not unique) 
b : bb -> . (b is not unique) 
c : cc -> . (c is not unique) 
d : cb -> d (d is unique) 

lub zwięźle

abcd -> ...d 

Może to myślenie życzeniowe, ale mam wrażenie, że nie powinno być elegancki i ogólnie rozwiązanie, które miałyby zastosowanie do dowolnie duża lista ciągów (lub liczb binarnych). Ale jeśli jest, nie byłem jeszcze w stanie tego zobaczyć.

Mam nadzieję, że wykorzystam ten algorytm, aby wyprowadzić minimalne sygnatury z kolekcji unikatowych obrazów (bitmap) w celu sprawnej identyfikacji tych obrazów w przyszłości. Gdyby w przyszłości wydajność nie była problemem, użyłbym prostego skrótu każdego obrazu.

Czy możesz poprawić brutalną siłę?

Edit Podejście mam ogrzaniu do buduje mapę pikseli obrazów

sprawl[Tuple<x=10, y=33,color=f1fefd>] => { 
    image17, 
    image23, 
    ... 
} 

sprawl[Tuple<x=10, y=34,color=f1fef0>] => { 
    image11 
    ... 
} 

a następnie za pomocą tej mapy, aby określić minimalny zestaw sygnatur pikseli dla każdego obrazu.

Jeśli piksel (oznaczony przez x, y, kolor) odwołuje się do jednego obrazu, to znalazłem idealną (minimalną) sygnaturę dla tego obrazu.

To jest bardziej skomplikowane, jeśli obraz nie ma unikatowych pikseli, ale ponieważ wiem, że wszystkie obrazy są unikatowe na liście, powinienem móc połączyć dwa lub więcej odnośników pikseli (ale tak mało jak to możliwe), aby wydedukować obraz.

Aktualizacja

pracuję na algorytmie do tego. Mój problem jest bardzo podobny do this one, a mój algorytm został zapisany jako answer to that question. Ta aktualizacja ma na celu zwrócenie uwagi każdego, kto nadal go obserwuje (widzę pięć zakładek). Pracuję nad tym w odosobnieniu, więc wszelkie opinie są mile widziane, nawet jeśli tylko zauważam, że nie wyraziłem się jasno!

Answer 1

Możesz wygenerować tablicę dwuwymiarową, która będzie zawierała liczbę razy, gdy każdy znak pojawi się w każdej pozycji (0-3). Na przykład arr[1,3] będzie zawierał liczbę razy, gdy cyfra/znak 1 pojawi się na ostatniej pozycji.

Następnie dla każdego ciągu s, przejdź przez wszystkie znaki w ciągu znaków.Te, które pojawiają się tylko raz w tej pozycji zgodnie z tablicą, są unikalnymi znakami dla tego ciągu. Innymi słowy, jeśli arr[s[i], i]==1 Następnie ciąg s jest unikalny w pozycji i.

Daje to rozwiązanie w czasie liniowym, podczas gdy algorytm, który podałeś, będzie zajmował kwadrat.

Answer 2

Jeśli Twoim celem jest późniejsza identyfikacja obrazów, możesz utworzyć bardzo szybki skrót obrazu, wybierając predefiniowane punkty, które będą służyć jako piksele tożsamości.

na przykład, można mieć strukturę (klasa, struct, nie ma znaczenia w jakim języku) w następujący sposób:

structure ImageHash { 
    int x_pixels, y_pixels; 
    u_long hash; 
    void createHash(Image img) { 
     x_pixels = img.x_pixels; 
     y_pixels = img.y_pixels; 
     for(int i = 1; i < 5; i++) { 
      int x = x_pixels/i; 
      for(int j = 1; j < 5; j++) { 
       int y = y_pixels/j; 
       int r = img.getPixelRed(x,y); 
       int g = img.getPixelGreen(x,y); 
       int b = img.getPixelBlue(x,y); 
       hash = (hash * 31)^(r^g^b); 
      } 
     } 
    } 
} 

Ten rodzaj „hash” niekompletnego pozwala zidentyfikować ewentualne tożsamości, a następnie możesz wykonać kosztowne, pełne porównanie oszczędnie, jeśli zajdzie taka potrzeba.

Rozszerz niekompletny skrót, jeśli to konieczne.

Answer 3

Ten problem może zostać rozwiązany przez trie lub drzewo prefiksu.

Zobacz Trie - Wikipedia, the free encyclopedia

Przez 3 strun w swojej przykład:

abcd 
abcc 
bbcb 

zostanie przekształcony drzewa trie (gdzie^oznacza korzeń drzewa):

^--a-b-c-d 
\  \ 
    \  c 
    \ 
    b-b-c-b 

Ścieżka do węzła, w którym się rozgałęzia, jest wspólnym przedrostkiem. Węzeł po ostatnim punkcie rozgałęzienia powoduje, że dany ciąg jest unikalny. W tym przypadku są to d, c, b.

Zakładam, że kolejność ciągów znaków nie jest dla ciebie ważna, że ​​porównujesz wszystkie ciągi znaków, aby znaleźć niepowtarzalność, a nie tylko sąsiedni ciąg znaków.

Złożoność powinna wynosić O (n x m). Ale prawdopodobnie wpłynie na to domena znaków w łańcuchu.