Al encontrar los píxeles que hacen que una imagen sea única dentro de una lista, ¿puede mejorar la fuerza bruta?

Question

Supongamos que tengo una lista de cadenas, donde cada cadena es

• exactamente 4 caracteres de largo y
• único dentro de la lista.

Para cada una de estas cadenas, deseo identificar la posición de los caracteres dentro de la cadena que hacen que la cadena sea única.

Así que para una lista de tres cuerdas

abcd 
abcc 
bbcb 

Para la primera cadena que quiero para identificar el carácter en cuarta posición d desde d no aparece en la cuarta posición en cualquier otra cadena.

Para la segunda cadena, quiero identificar al personaje en la 4ta posición c.

Para la tercera cuerda que yo quiero para identificar el carácter en primera posición b y el carácter en 4ª posición, también b.

Esto podría representarse de forma concisa como

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

si se considera el mismo problema pero con una lista de números binarios

0101 
0011 
1111 

A continuación, el resultado que quiero sería

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

Manteniéndome con el tema binario, puedo usar XOR para identificar qué bits son únicos dentro de dos números binarios desde

0101^0011 = 0110 

que puedo interpretar en el sentido de que en este caso la 2ª y 3ª bits (lectura de izquierda a derecha) son únicos entre estos dos números binarios. Esta técnica podría ser una pista falsa, a menos que de alguna manera pueda extenderse a la lista más grande.

Un enfoque de fuerza bruta sería mirar cada cuerda a su vez, y para cada cadena iterar a través de las divisiones verticales del resto de las cadenas en la lista.

Así que para la lista

abcd 
abcc 
bbcb 

Me gustaría empezar con

abcd 

y recorrer las rebanadas verticales de

abcc 
bbcb 

donde serían estos cortes verticales

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

o en forma de lista, "ab", "bb", "cc", "cb".

Esto daría lugar a cuatro comparaciones

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

o concisa

abcd -> ...d 

Tal vez sea una ilusión, pero tengo la sensación de que no debe haber una solución elegante y general que se aplicaría a una lista arbitrariamente grande de cadenas (o números binarios). Pero si es que aún no he podido verlo.

Espero utilizar este algoritmo para derivar firmas mínimas de una colección de imágenes únicas (mapas de bits) con el fin de identificar de manera eficiente esas imágenes en el futuro. Si la eficiencia futura no fuera una preocupación, usaría un hash simple de cada imagen.

¿Se puede mejorar la fuerza bruta?

Editar El enfoque que estoy calentando a es la construcción de un mapa de píxeles para imágenes

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

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

y luego usar ese mapa para identificar el conjunto mínimo de píxeles de firma para cada imagen.

Si un píxel (identificado por x, y, color) hace referencia a una sola imagen, entonces he encontrado una firma perfecta (mínima) para esa imagen.

Es más complicado si una imagen no tiene píxeles únicos, pero como sé que todas las imágenes son únicas dentro de la lista, podría combinar dos o más referencias de píxeles (pero la menor cantidad posible) para deducir la imagen.

actualización

He estado trabajando en un algoritmo para esto. Mi problema es muy similar al this one, y he escrito mi algoritmo como answer to that question. Esta actualización es para llamar la atención de cualquier persona que siga (veo cinco marcadores). Estoy trabajando en esto de forma aislada, por lo que cualquier comentario es bienvenido, ¡aunque solo sea para observar que no me he aclarado!

Answer 1

Puede generar una matriz bidimensional que contendrá el número de veces que aparece cada carácter en cada posición (0-3). Por ejemplo, arr[1,3] contendrá la cantidad de veces que el dígito/carácter 1 aparece en la última posición.

Luego, para cada cadena s, repase todos los caracteres de la cadena.Los que aparecen solo una vez en esa posición de acuerdo con la matriz son los caracteres únicos de esa cadena. En otras palabras, si arr[s[i], i]==1 Entonces la cadena s es única en la posición i.

Esto le dará la solución en tiempo lineal, mientras que el algoritmo que proporcionó tomará un tiempo cuadrático.

Answer 2

Si su objetivo es identificar imágenes más tarde, puede crear un hash muy rápido de la imagen eligiendo puntos predefinidos para que sirvan como píxeles de identidad.

por ejemplo, usted podría tener una estructura (clase, estructura, no importa qué idioma) de la siguiente manera:

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); 
      } 
     } 
    } 
} 

Esta especie de "picadillo incompleta" le permitirá identificar posibles identidades, y luego puede hacer la costosa comparación total con moderación según sea necesario.

Amplíe el hash incompleto según sea necesario.

Answer 3

Este problema puede ser resuelto por trie, o el árbol de prefijos.

Ver Trie - Wikipedia, the free encyclopedia

Para las 3 cadenas en el ejemplo:

abcd 
abcc 
bbcb 

se convirtió en un árbol trie (donde^denota la raíz del árbol):

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

La ruta al nodo donde se ramifica es el prefijo común. El nodo después del último punto de ramificación es lo que hace que una cadena en particular sea única. En este caso, son d, c, b.

Supongo que el orden de la cadena no es importante para usted, que compara todas las cadenas para encontrar la singularidad, no solo la cadena vecina.

La complejidad debe ser O (n x m). Pero esto probablemente se verá afectado por el dominio de los caracteres en su cadena.