inteligentne obcinanie ścieżki/elipsa do wyświetlania

Question

Poszukuję algorytmu obcinania ścieżek (podobnie jak w przypadku statycznego sterowania Win32 z SS_PATHELLIPSIS) dla zestawu ścieżek, które powinny skupiać się na różnych elementach.

Na przykład, jeśli moje ścieżki są tak:

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/ 

Kiedy nie wystarczająco dużo miejsca wyświetlacz jest dostępne, powinny być obcięte do czegoś takiego:

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

(Przyjmując, że wielokropkiem zazwyczaj jest krótszy niż trzy litery).

To tylko przykład dość prostego, idealnego przypadku (np. Wszystkie będą teraz kończyły się w różnych długościach i nie będę wiedział, jak stworzyć dobrą sugestię, gdy ścieżka "Thingie/Long Test/"jest dodawany do puli).

Brak określonej struktury elementów ścieżki, są one przypisane przez użytkownika, ale często elementy będą miały podobne segmenty. Powinien działać dla czcionek proporcjonalnych, więc algorytm powinien przyjąć funkcję pomiaru (i nie wywoływać go zbyt mocno) lub wygenerować listę sugestii.

Dane - typowy przypadek użycia zawierałby 2,4 segmenty ścieżki i 20 elementów na segment.

Poszukuję wcześniejszych prób w tym kierunku, a jeśli to rozwiąże problem z rozsądną ilością kodu lub zależności.

Answer 1

Zakładam, że pytasz głównie o to, jak sobie poradzić z zestawem nazw folderów wyodrębnionych z tego samego poziomu hierarchii, ponieważ podział według wierszy i separatorów ścieżek oraz agregacja według głębokości hierarchii jest prosta.

Twój problem przypomina mi wiele do longest common substring problem, z różnicami, że:

1. jesteś zainteresowany w wielu podciągi, a nie tylko jeden.
2. Dbacie o zamówienie.

Mogą się wydawać istotne, ale jeśli przyjrzysz się rozwiązaniu z zakresu programowania dynamicznego w artykule, zobaczysz, że obraca się wokół tworzenia tabeli "kolizji znaków", a następnie szuka najdłuższej przekątnej w tej tabeli. Myślę, że można zamiast tego wyliczyć wszystkie przekątne w tabeli według kolejności, w jakiej się pojawiają, a następnie dla każdej ścieżki zastąpić, kolejno, wszystkie wyrazy tych ciągów za pomocą elips.

Egzekwowanie minimalnej długości podciągu równej 2 spowoduje zwrócenie wyniku podobnego do podanego w pytaniu.

Wygląda na to, że wymaga jakiegoś majsterkowania z algorytmem (na przykład, upewniając się, że pewien podciąg jest pierwszy we wszystkich ciągach), a następnie musisz wywołać go w całym zestawie ... Mam nadzieję, że to przynajmniej daje ty możliwy kierunek.

Answer 2

Cóż, część zamawiająca "liczba naturalna" jest w rzeczywistości łatwa, wystarczy zamienić wszystkie liczby na sformatowaną liczbę, gdzie jest wystarczająco dużo wiodących zer, np. Test 9V ->Test 000009V i Test 12B ->Test 000012B. Można je teraz sortować za pomocą standardowych metod.

Dla rzeczywistej elipsyzacji.O ile nie jest to tak naprawdę olbrzymi system, po prostu dodaję ręczną elipsyzującą "listę" (z wyrażeń regularnych, dla elastyczności i bólu), które zamieniają określone słowa w elipsy. To wymaga ciągłej pracy, ale wymyślanie algorytmu pochłania również Twój czas; są miriady skrzyń narożnych.

Prawdopodobnie wypróbuję metodę "Floodfill". Ułóż pierwszy poziom katalogów tak, jakbyś był mapą bitową, każda litera jest pikselem. iteruj po wszystkich znakach znajdujących się w nazwach katalogów. we wszystkich z nich "pomaluj" tę samą postać, a następnie "pomaluj" następną postać z pierwszego ciągu, tak aby podążał za poprzednią postacią (i tak dalej itd.). Następnie wybierz najdłuższy napis malowany, który znajdziesz.

Przykład (z prefiksem *, to malowane)

Foo 
BarFoo 

*Foo 
Bar*Foo 

*F*oo 
Bar*F*oo 

... 

zauważyć, że:

*ofoo 
b*oo 

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

of*oo 
b*oo 
... 

a następnie dostać się do drugiej "o" i znajdzie podciąg co najmniej 2. Będziesz musiał wykonać iteracje na większości możliwych instancji znaku (jedna optymalizacja ma zatrzymać się w każdym ciągu w pozycji Length-n, gdzie n jest najdłuższym znalezionym wspólnym podciąganiu.Ale jest jeszcze inny problem (tutaj z "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 

Co chcesz zrobić? Wytnij Alfa Beta Gamma Delta lub Alfa Beta lub Beta Beta lub Beta?

Jest to nieco chaotyczne, ale może być zabawne :).