интеллектуальное усечение пути/эллипсис для отображения

Question

Я ищу алгоритм усечения пути существования (аналогично статическому управлению Win32 с SS_PATHELLIPSIS) для набора путей, которые должны фокусироваться на отдельных элементах.

Например, если мои пути, как это:

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/ 

Когда не хватает отображения свободного места, то они должны быть усечены на что-то вроде этого:

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

(Предполагая, что многоточие обычно короче трех букв).

Это всего лишь пример довольно простого, идеального случая (например, теперь все они будут иметь разную длину, и я не знаю, как создать хорошее предложение, когда путь «Thingie/Long Test/"добавляется в пул).

Нет данной структуры элементов пути, которую они назначают пользователем, но часто элементы будут иметь одинаковые сегменты. Он должен работать для пропорциональных шрифтов, поэтому алгоритм должен принимать мерную функцию (и не называть ее сильно) или генерировать список предложений.

Типичный пример использования данных будет содержать 2..4 сегментов пути и 20 элементов на сегмент.

Я ищу предыдущие попытки в этом направлении, и если это разрешимо с разумным количеством кода или зависимостей.

Answer 1

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

Ваша проблема напоминает мне о longest common substring problem, с разницей, что:

1. вы заинтересованы во многих подстрок, а не только один.
2. Вы заботитесь о заказе.

Это может показаться существенным, но если вы изучите решение динамического программирования в статье, вы увидите, что оно вращается вокруг создания таблицы «столкновений персонажей», а затем ищет самую длинную диагональ в этой таблице. Я думаю, что вы могли вместо этого перечислить все диагонали в таблице порядком, в котором они появляются, а затем для каждого пути замените, по порядку, все проявления этих строк с эллипсами.

Выполнение минимальной длины подстроки 2 возвращает результат, аналогичный тому, что вы указали в своем вопросе.

Кажется, что это требует некоторого вмешательства в алгоритм (например, обеспечение определенной подстроки первой во всех строках), а затем вам нужно вызвать ее по всему вашему набору ... Надеюсь, это по крайней мере дает вам возможное направление.

Answer 2

Ну, часть заказа «натурального числа» на самом деле проста, просто замените все номера на форматированное число, где есть достаточное количество нулей, например. Test 9V ->Test 000009V и Test 12B ->Test 000012B. Теперь они сортируются стандартными методами.

Для фактического эллипсирования.Если это фактически не огромная система, я бы просто добавил ручной эллипсизирующий «список» (регулярных выражений, для гибкости и боли), которые превратили бы определенные слова в эллипсы. Это требует непрерывной работы, но придумывание алгоритма также ест ваше время; есть мириады угловых дел.

Я бы, наверное, попробовал подход «Наводнение». Упорядочить первый уровень каталогов, как и растровое изображение, каждая буква - это пиксель. перебирать все символы, которые находятся в именах каталогов. со всеми из них «нарисуйте» этот же символ, затем «нарисуйте» следующий символ из первой строки, чтобы он следовал за этим предыдущим символом (и т. д. и т. д.). Затем выберите самую длинную окрашенную строку, которую вы найдете.

Пример (если префикс *, она написана)

Foo 
BarFoo 

*Foo 
Bar*Foo 

*F*oo 
Bar*F*oo 

... 

обратите внимание, что:

*ofoo 
b*oo 

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

of*oo 
b*oo 
... 

И тогда вы получите на втором «о», и он будет найти подстроку по крайней мере, 2. Итак, вам придется перебирать наиболее вероятные экземпляры символов (одна оптимизация должна останавливаться в каждой строке в позиции Length-n, где n является самой длинной уже найденной общей подстрокой. Но тогда есть еще одна проблема (здесь с "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 

Что вы хотите сделать? Вырезать Alfa Beta Gamma Delta или Alfa Beta или Beta Beta или Beta?

Это немного бессвязно, но может быть интересно :).