2
$\begingroup$

Question:

I want to construct a optimal directory tree structure to access $n$ ($n < 256$) elements using only the keyboard with as few key presses as possible. For this one could consider the directory as double linked list with connections between the first and the last element. To access element E, one then would traverse the list until the appropriate subdirectory S, enter S and restart from there until E is selected.

There are some natural requirements:

  • the elements in the tree structure are lexicographically ordered
  • the arity of the tree might be >2.
  • I would like to apply custom weights to some elements
  • the cost to be minimised is the weighted average of the total click count to access all elements (i.e. $c = \sum_{e \in E} w(e)*c(e)$, where $E$ is the set of elements, $w(\cdot)$ the weight for each element and $c(\cdot)$ the cost to access each element. $c(\cdot)$ depends on the chosen directory structure, of course.)

I'm struggling to find a good solution here. I do not know any standard tree that would fit in here as there might be no elements in intermediate nodes.

So, I'm looking for hints to literature. Maybe someone even knows an efficient algorithm? Bruteforce in Python takes too long to run, Bruteforce in C++ take too long to code :).

Motivation

I feed my stereo from a single board computer using the DLNA protocol. I want to access my music (artist-folders are the elements) as fast as possible. The stereo only supports "up", "down", "enter" and "escape" to navigate.

Clarifications

$c(e)$ is the number of clicks needed to access element $e$ from the top of the directory. $c(\cdot)$ depends on the directory structure. To access the lexicographically third element in a long list, one needs exactly 3 clicks (2x down, 1x enter). For the directory structure $((a, b), (c, d))$ one would only need 2 clicks to enter $c$ (2x enter).

Naming the subdirectories will not be a problem. Since the elements keep their order, I can use the names of the first and the last elements, as in a dictionary.

$\endgroup$
  • $\begingroup$ Your problem is not completely well-defined, which makes it hard to answer. In particular, what is exactly $c(e)$? $\endgroup$ – Yuval Filmus Jul 17 '17 at 12:42
  • $\begingroup$ Your problem is reminiscent of Huffman coding and similar problems, though it's hard to tell exactly until you define the problem completely. $\endgroup$ – Yuval Filmus Jul 17 '17 at 12:42
  • $\begingroup$ I added some clarifications and hope that they help. $\endgroup$ – Max Görner Jul 17 '17 at 18:36
2
$\begingroup$

One way is to use a Huffman code, over an alphabet of size $k$, whre $k$ is the number of letters you're willing to use on the keyboard. Make the weight for an entry be the "probability" for that entry (how often that entry is selected). Then a Huffman code will minimize the expected number of key presses. There's a standard algorithm for constructing a Huffman code.

The potential drawback is that it doesn't use the keys of the keyboard in the way you suggest; rather than using up/down to move forward/backward in a directory, the $k=4$ keys are all treated as equal, and each keypress moves you one level down in the tree. In other words, each directory has at most $k$ entries, and you select an entry with a single keypress. You might or might not be happy with the user experience. If you prefer, you can set $k=2$ and use only the up/down keys for selection (each directory has two entries; press 'up' to select the first or 'down' to select the second, and it will jump immediately to that entry). This will require fewer key presses than the approach you are imagining, but does require you to find a way to name each of the resulting nodes in the tree with a human-understandable category (i.e., pick a name for that directory/entry).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.