6
$\begingroup$

I'm trying to find or create an algorithm for efficiently displaying text that is word wrapped. All the algorithms (if they an even be called that) for word wrapping presume a given lot of text and window size, and compute word wrapping in $O(n)$ time. That isn't realistic because text can be huge, users can modify text anywhere, and window sizes can change. It is quite a problem to expect $O(n)$ modification time whenever something changes. When a user modifies the text or resizes a window, I'd like to be able to update the display in something like logarithmic time.

Here is how I formalize the a slightly simplified version of the problem:

$A$ is an array of positive integers that of length $n$. It represents the lengths of words (and their trailing space). $W$ is a positive integer representing window size. For simplicity assume $W \ge \max(A)$. Each query of $I_W$ represents fetching the word at the start of a line. A modification of $A$ is like user modifying the text, and a modification of $W$ is like the window being resized.

I want to be able to repeatedly do queries and modifications of $A$. A modification is the insertion, deletion, or modification of an integer in $A$. A query is a request of $I_W[k] \in \mathbb N$, defined as

  • $I_W[0] = 0$
  • $I_W[k+1] = \text{ the biggest } z \text{ s.t. } \sum_{I_{k} \le j < z} A[j] \le W$

To describe $I_W$ another way, suppose $A$ is $[5, 3, 4, 6, 5, 1, 1, 4, 4, \cdots]$ and $W = 9$. Then split $A$ into initial segments whose sums are $\le W$, so $[[5, 3], [4], [6], [5, 1, 1], [4, 4], \cdots]$, then $I_W(k)$ is the sum of the lengths of the first $k+1$ splits; that is, $I_W = [0, 2, 3, 4, 7, 9, \dots]$.

I'm looking for an algorithm and datastructure that would allow for linearithmic preprocessing on $A$ and something like logarithmic time modifications and queries. I'd also like to be able to handle changes in $W$ quickly but that can somewhat be handled with threads and software design so it isn't as important.

The fact that even tiny modifications of $A$ can have a tiny or drastic impact on $I_W$ is making this fairly challenging for me.

$\endgroup$
12
  • $\begingroup$ This is not from any programming contest even if it uses some of the same language (like query). I'd appreciate any help tagging this question appropriately. $\endgroup$
    – DanielV
    Oct 4, 2020 at 20:40
  • $\begingroup$ are you sure that you are looking for the smallest $z$ such that the sum of the length of the word is smaller than $W$? I think you are looking for the biggest $z$ (you try to fully use the space right?) $\endgroup$
    – plshelp
    Oct 4, 2020 at 23:06
  • $\begingroup$ Ah you are right, it is the largest z. $\endgroup$
    – DanielV
    Oct 4, 2020 at 23:35
  • $\begingroup$ Is your algorithm relevant for a "real" application? If so notice that only the text on the screen actually need to be aligned, which means every thing that's not displayed would not be relevant and usually the amount of text on a single screen is not enough to require faster than $O(n)$ aligning (you need to render the text anyway). Of course theoretically your question is still interesting, I'm just curious. $\endgroup$
    – plshelp
    Oct 4, 2020 at 23:55
  • 2
    $\begingroup$ The amount of text before is relevant because resizing the screen could make the previous text affect how the current text is displayed. And modification of initial text + scroll to end would affect how later text is displayed. $\endgroup$
    – DanielV
    Oct 5, 2020 at 0:43

1 Answer 1

3
$\begingroup$

I think you can handle single-word modifications in $O(d \log n)$ time, where $d$ (density) is the maximal number of words in a line, which is hopefully small for any reasonable $A$ and fixed $W$.

Let's take one of your sentences as an example. We want it to be wrapped with $W = 30$ characters like this:

I'm looking for an algorithm
and datastructure that would
allow for linearithmic
preprocessing on A and
something like logarithmic
time modifications and
queries.

First, let's find all possible lines. This can be done greedily in $O(n)$ using two pointers scanning through $A$. If one of these lines ends where the other begins, we connect them.

Tree of all possible wrappings

The path from node $1$ to the root of the tree represents $I_W$.

Now let's remove "an" from the first line, forcing all other lines to shift:

I'm looking for algorithm and
datastructure that would allow
for linearithmic preprocessing
on A and something like
logarithmic time modifications
and queries.

But here's one nice thing about the tree: any single-word change can only affect $O(d)$ edges. We find these edges by re-running the same pre-processing on a small window around the changed word. In our case, the changes are:

  • Edge 1-6 removed
  • Edge 4-8 removed
  • Edge 1-7 added

Tree after the word has been removed

So, we need to be able to do these operations efficiently:

  1. Add new edge into the tree
  2. Remove existing edge from the tree
  3. Find $k$-th ancestor of a given node.

All these operations can be done in $O(\log n)$ via Euler tour technique. I won't describe its implementation in detail, but feel free to ask a separate question about it.

$\endgroup$
5
  • $\begingroup$ I think I get what you are saying. Let me mess with it a while, thanks. One thing I like about this is that it seems to not depend on the unit used to measure the size of words, such as pixels instead of characters. $\endgroup$
    – DanielV
    Oct 17, 2020 at 15:39
  • $\begingroup$ Taking the first graph as an example, it isn't obvious to me how the question "what is the fifth line?" can be answered "17 something" in less than $n/d$ time. Can't really binary search a linked list. Am I missing something? $\endgroup$
    – DanielV
    Oct 17, 2020 at 16:42
  • $\begingroup$ @DanielV that's why I suggest to store the tree as its Euler Tour in a balanced binary search tree. The operation you ask about is "find k-th ancestor". $\endgroup$ Oct 17, 2020 at 17:21
  • $\begingroup$ Ah I see what you mean now. $\endgroup$
    – DanielV
    Oct 17, 2020 at 17:39
  • 1
    $\begingroup$ Really cool approach! $\endgroup$ Oct 18, 2020 at 13:18

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.