Databases
StackOverflow2013
Postsdbo
POResolving ambiguous categories in an ordered list
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POResolving ambiguous categories in an ordered list
    text
    copied!<p>Let's take a concrete example and hope I can be clear. Suppose the (ordered) list of months:</p> <blockquote> <p>January &lt; February &lt; March &lt; ... &lt; December</p> </blockquote> <p>(with integers that stand for the months, zero-based), such that </p> <blockquote> <p>Jan is 0, Feb is 1, ..., Dec is 11.</p> </blockquote> <p>Now suppose I do not have access to the full names of months, and am given the following list, where months have been shortened to their first letter, and <em>e</em> stands for an empty category, like this:</p> <blockquote> <p>e, F, e, e, e</p> </blockquote> <p>If I build a list of "unambiguous months" (f:1, s:8, o:9, n:10, d:11), I can fill the empty categories by by first calculating the first category (using subtraction and mod 12), and then write the rest from there. However, suppose I am given the list</p> <blockquote> <p>e, A, e, e, J, e</p> </blockquote> <p>Then I can (intuitively) calculate that although <em>A</em> is ambiguous (could be April or August), in this context it can only be April, since August does not have any <em>J</em>s following it after 2 categories. Once I find this, I can again calculate everything from the start. </p> <p>My question, finally, is: is there an analytic solution (function, algorithm) for this problem, or is my only hope to use brute force to define each potential relation? For some examples, no disambiguation algorithm/function can work: consider the case where I have a <em>J</em> followed by 11 <em>e</em>'s, followed by a <em>J</em> followed by 11 <em>e</em>'s ... Since there is a year in between, I cannot disambiguate <em>J</em> into January, June or July. </p> <p><strong>Answer</strong>: I ended up coding Il-Bhima's answer, because for this case in particular, regex's are ok, even at a higher running time O(mn). However, I accepted Ben's answer as the correct answer because it subsumes the others (mentions the regex solution), but also suggests a better way by using the KMP algorithm O(m+n), although this is for larger numbers of the string against to match the pattern. Thanks, everybody.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload