If we want to map abbreviations of full-English words (e.g. map "Jan" to "January"), how can we identify abbreviations which map to multiple words?

Question

Short Version:

How can we construct a trie which maps abbreviations of names-of-the-month to full-month (we map the abbreviation "mar" to "march")?

• The set of all abbreviations is formed by:
  • keeping the first letter of the month name. (all abbreviations of "january" begin with "j")
  • deleting 1 or more characters ("jan" deletes "uary" from "january"; "jar" deletes "nuay" from "january")

The Long Version:

How can we construct such a trie?
What algorithm will build the appropriate trie from the container of verbose strings?

Consider the English names for months of the year:

• January
• February
• March
• April
• [... truncated ...]
• October
• November
• December

We find it useful say that the English names for months of the year are "verbose" strings.
For any "verbose" string $v$, and any string $a$ we say that $a$ is an "abbreviation" of $v$ if and only if all of the following conditions are met:

• $a$ non-empty. $|a| \geq 1$
• $a$ can formed by deleting 1 or more characters from "verbose" string $v$
• $a(1) = v(1)$. Assume that string indexing begins at $1$, and not $0$.

For example, "jan" is an abbreviation of "january."

Suppose you want to write an algorithm which:

• accepts a list of verbose strings as inputs.
• the algorithm outputs a "trie" data-structure (information retrieval tree) $T$ such that:
  • The trie $T$ accepts any ASCII string as input.
  • An output (leaf node) of the trie should be set of strings $S$ such that:
    • every string in $S$ is a verbose string
    • the string fed as input into trie $T$ is an abbreviation of every verbose string in container $S$

Some examples of input to the trie and output of the trie are shown below:

• Example 1

  • Input: "Ma"
  • Output: $\{$"March", "May"$\}$

• Example 2

  • Input: "Mar"
  • Output: $\{$"March"$\}$

• Example 3

  • Input: "Decuary"
  • Output: $\{$" "$\}$ ..... the empty-set

The output from the trie should be one of:

• the empty set
• a set of one item
• a set of two or more items

For months of the year, an application might be a web-page where end-user can type in any half-way reasonable date-format, instead getting an error message.

If you do not like the months of the year application, a different use-case would be to write write your own Linux Shell (similar to BASH). Maybe any half-way reasonable abbreviation of "make directory" will map to "mkdir" In that case, we could have many-to-one mapping from high-level shell-commands to low-level Linux commands.

The question is:

How can we construct such a trie?
What algorithm will build the appropriate trie from the container of verbose strings.

Also, can we avoid brute-force generating a list of all abbreviations before-hand? The set of all strings form-able by deleting 1 or more characters from the verbose strings is quite large. We would like to avoid combinatorial explosion, if we can.

I am looking for an algorithm, not code written in any specific language.

Additional Applications (Edit from October 30, 2020)

There are other practical applications than those I originally mentioned.

For example, suppose that you are trying to create a search engine which job applicants use to locate the name of the college they attended.

An example of a verbose string is "The University of Colorado at Denver".

In practice, end-users tend to delete letters from the verbose string. For example, and end-user might type in "UC Denver" or "University Colorado Denver".

---

Another application would be searching for mailing addresses.
An example, a "verbose" mailing address is shown below:

3751 North. Tower Road.\r\n
Aurora, Colorado\r\n
80011-3522\r\n
United States of America\r\n

End-users could write 3751 N Tower Rd.\r\nAurora, Colorado:

• "N" instead of "North"
• "Rd" instead of "Road"
• "CO" instead of "COLORADO"

Our search engine would still find the correct mailing addres. For this specific example end users could write a dot at the end of the "N" or simply a space character, and it would still work.

We assume that end-users always type in a valid mailing address, but with zero or more characters deleted.

We simply need to identify the set of verbose mailing address which the abbreviated mailing address maps to. If there is only one verbose mailing address, then we are in good shape. If there are 3 or 4 verbose mailing addresses, we could display them all, and ask the end-user to choose one.

Answer 1

Since the first symbol must match, we can just check it in the beginning, and solve the problem separately for each starting symbol (from here on, we just remove the starting letter from all strings).

First, let's start with without-trie intuition. As an example, consider all permutations of string $abbc$. All possible strings are the following:

$$S=\{\cdot abbc, \cdot abcb, \cdot acbb, \cdot babc, \cdot bacb, \cdot bbac, \cdot bbca, \cdot bcab, \cdot bcba, \cdot cabb, \cdot cbab, \cdot cbba\},$$

where by $\cdot$ I denote our current position in these strings (initially, we are at the beginning of all strings). Now, assume that the symbol $b$ arrives. For each string, we find the first position of $b$ after $\cdot$, and move there. I.e.

$$S_b=\{ab \cdot bc, ab \cdot cb, acb \cdot b, b \cdot abc, b \cdot acb, b \cdot bac, b \cdot bca, b \cdot cab, b \cdot cba, cab \cdot b, cb \cdot ab, cb \cdot ba\}$$

Assume that the symbol $a$ arrives next. Again, we find the next position of $a$ after $\cdot$ in all strings. Strings that don't have such positions disappear from our set.

$$S_{ba}=\{ba \cdot bc, ba \cdot cb, bba \cdot c, bbca \cdot, bca \cdot b, bcba \cdot, cba \cdot b, cbba \cdot \}$$

If symbol $b$ arrives next, we have

$$S_{bab}=\{bab \cdot c, bacb \cdot, bcab \cdot, cbab \cdot\}$$

Solution with trie. Actually, the solution above already works, but it may require $O(\sum_s len(s))$ time (and it often will). We can do better with tries.

First, we build a trie for our strings.

After we have an input symbol $b$, we want to find nodes corresponding to $S_b$ (they are circled on the picture). On each branch, we want to find all nodes which go first after some $b$. Therefore, for each node $u$, we have to find all nodes $v$ such that there exists path $u \leadsto \ldots \to^b v$, and there is no another such node on the path. For example, while for node $9$ there is such path from the root, there is another such node ($8$) on its path.

We have to find all such nodes for all nodes and symbols. I.e. $next[u][c]$ denotes the set of nodes in a subtree of $u$ which go first after symbol $c$. E.g. \begin{align*} next[0][b] &= \{2, 8, 10, 28, 30\} \\ next[2][c] &= \{4, 5\} \\ next[26][a] &= \{27, 31, 34\} \end{align*}

This is a pseudo-code how it can be done ($sym(u)$ denotes a symbol by which precedes the node $u$. E.g. $sym(1)=a$, $sym(2)=b$):

for each node u:
    next[u] = {}

def dfs(u, stack):  # stack stores all ancestors of the current node
    c = sym(u)
    for v in stack:
        next[v][c].insert(u)
        if sym(v) == c:
            break  # for all nodes above, v is before u and has the same symbol

    for v in children(u):
        dfs(v, u :: stack)  # add u to stack

dfs(root, [])

Now, when we have a string $s$ as an input, finding an answer is as simple as:

nodes = [root]
for c in s:
    nodes = Union(next[node][c] for node in nodes)

return nodes

, where $next[node][c]$ returns an empty set when it doesn't exists.

Optimization? (I'll update this section if I prove the statements here) While this code works, we may have large intermediate solutions but result in the empty set. One way to avoid it is to do some preprocessing: namely, build a DFA. Each state corresponds to a set of nodes, and transitions are as described in the second algorithm. I think it can be shown that the number of such states depends linearly on the total length of the strings. You also need to store a mapping from states to sets of nodes, and I think it'll also be linear in the total length of the strings.

Answer 2

This is in the end a programming question, and programming has to be effective - produce the result, minimising the cost, which is mostly the cost of programming.

For 12 items you don’t create any complex data structure. For example, in Swift you would write

let months = [“January”, “February”].filter { $0.hasPrefix(“J”) }

and you’re done. But what you plan doesn’t work anyway. For example, in German “März” is abbreviated as “Mrz”, not “Mär”. And typically the abbreviations used are fixed, not arbitrary numbers of letters.