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
"$\}$
- Input: "
Example 2
- Input: "
Mar
" - Output: $\{$"
March
"$\}$
- Input: "
Example 3
- Input: "
Decuary
" - Output: $\{$"
- Input: "
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.
quick-sort
,the simplex algorithm
,the Needleman-Wunsch algorithm
, and more. Are questions about algorithms not allowed on the computer science branch of stackechange? $\endgroup$