Truncamiento/elipsis de ruta inteligente para la pantalla

Question

Estoy buscando un algoritmo de truncamiento de ruta existente (similar a lo que hace el control estático de Win32 con SS_PATHELLIPSIS) para un conjunto de rutas que deben centrarse en los distintos elementos.

Por ejemplo, si mis caminos son así:

Unit with X/Test 3V/ 
Unit with X/Test 4V/ 
Unit with X/Test 5V/ 
Unit without X/Test 3V/ 
Unit without X/Test 6V/ 
Unit without X/2nd Test 6V/ 

Cuando no haya suficiente espacio de visualización está disponible, deben ser truncado a algo como esto:

...with X/...3V/ 
...with X/...4V/ 
...with X/...5V/ 
...without X/...3V/ 
...without X/...6V/ 
...without X/2nd ...6V/ 

(Suponiendo que una elipsis generalmente es más corto que tres letras).

Esto es solo un ejemplo de un caso ideal bastante simple (por ejemplo, todos terminarían en diferentes longitudes ahora, y no sabría cómo crear una buena sugerencia cuando un camino "Thingie/Long Test/"se agrega al grupo).

No hay una estructura dada de los elementos de ruta, los asigna el usuario, pero a menudo los elementos tendrán segmentos similares. Debería funcionar para fuentes proporcionales, por lo que el algoritmo debería tomar una función de medida (y no llamarla demasiado) o generar una lista de sugerencias.

En términos de datos, un caso de uso típico contendría 2..4 segmentos de ruta y 20 elementos por segmento.

Estoy buscando intentos previos en esa dirección, y si eso se puede resolver con una cantidad razonable de código o dependencias.

Answer 1

Estoy asumiendo que estás pidiendo principalmente acerca de cómo tratar con el conjunto de nombres de carpetas extraídos del mismo nivel de jerarquía, desde que se separó por filas y separadores de ruta y la agregación por la profundidad jerarquía es simple.

Su problema me recuerda mucho a la longest common substring problem, con las diferencias que:

1. usted está interesado en muchos subcadenas, no sólo uno.
2. Le importan las órdenes.

Estos pueden aparecer sustancial, pero si se examina la solución de programación dinámica en el artículo se puede ver que gira en torno a la creación de una tabla de "colisiones de carácter" y luego en busca de la mayor diagonal en esta tabla. Creo que en su lugar podría enumerar todas las diagonales en la tabla por el orden en que aparecen, y luego, para cada ruta, reemplazar, por orden, todas las apariencias de estas cadenas con puntos suspensivos.

Aplicar una longitud mínima de subcadena de 2 devolverá un resultado similar al que ha descrito en su pregunta.

Parece que requiere algunos retoques con el algoritmo (por ejemplo, asegurar que cierta subcadena sea la primera en todas las cadenas), y luego debe invocarla sobre todo su conjunto ... Espero que esto al menos brinde usted una posible dirección.

Answer 2

Bueno, la parte del pedido de "número natural" es realmente fácil, simplemente reemplace todos los números con el número formateado donde hay suficientes ceros a la izquierda, ej. Test 9V ->Test 000009V y Test 12B ->Test 000012B. Estos ahora son ordenables por métodos estándar.

Para la real elipsis.A menos que este sea en realidad un sistema enorme, simplemente agregaría una "lista" elipsis manual (de expresiones regulares, para flexibilidad y dolor) que convertiría ciertas palabras en elipses. Esto requiere un trabajo continuo, pero encontrar el algoritmo también consume tu tiempo; hay miríadas de casos de esquina.

Probablemente probaría un enfoque de "Floodfill". Organice el primer nivel de directorios como lo haría con un mapa de bits, cada letra es un píxel. iterar sobre todos los caracteres que están en los nombres de los directorios. con todos ellos, "pintar" este mismo personaje, luego "pintar" el siguiente carácter de la primera cuerda de forma que siga a este personaje anterior (y así sucesivamente, etc.) Luego seleccione la cadena pintada más larga que encuentre.

Ejemplo (si el prefijo *, está pintado)

Foo 
BarFoo 

*Foo 
Bar*Foo 

*F*oo 
Bar*F*oo 

... 

nota que:

*ofoo 
b*oo 

*o*foo 
b*oo 
.. painting of first 'o' stops since there are no continuing characters. 

of*oo 
b*oo 
... 

Y entonces se llega a la segunda "o" y que se encuentra una subcadena de al menos 2. Por lo tanto, tendrá que iterar sobre la mayoría de las instancias de caracteres posibles (una optimización es detenerse en cada cadena en la posición Length-n, donde n es la subcadena común más larga ya encontrada. Pero hay otro problema más (aquí con "Beta Beta")

  | <- visibility cutout 
Alfa Beta Gamma Delta 1 
Alfa Beta Gamma Delta 2 
Alfa Beta Beta 1 
Alfa Beta Beta 2 
Beta Beta 1 
Beta Beta 2 
Beta Beta 3 
Beta Beta 4 

¿Qué desea hacer? Cortar Alfa Beta Gamma Delta o Alfa Beta o Beta Beta o Beta?

Esto es un poco divagante, pero podría ser entretenido :).