TADM2E 4.45 - Revision history

Matt: Undo revision 1011 by MattWars (talk)

2020-07-28T09:56:46Z

Undo revision 1011 by MattWars (talk)

MattWars at 07:14, 28 July 2020

2020-07-28T07:14:44Z

Joky: Put first the best solution and fix the complexity of the second one.

2016-12-30T22:33:34Z

Put first the best solution and fix the complexity of the second one.

Aceyogi at 14:16, 15 July 2016

2016-07-15T14:16:09Z

Murrayc: fix typo

2015-11-05T12:19:12Z

fix typo

MagalooXX: added python source formatting

2014-10-13T16:22:38Z

added python source formatting

Algowikiadmin: Recovering wiki

2014-09-11T18:24:03Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:14:18Z

Recovering wiki

New page

Let's use the example given, for words say <i>A, B, C</i>, in the problem but not get too tied to the specific values. It helps to think about sorting the search string words by their indexes in the document:

<pre>
A C B A A C * * B B * * * * C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
</pre>

In the code example this is just a call to sort but since each word index list is sorted we could use <code>MergeSort</code> which means this portion of the code is <math>\mathcal{O}(n)</math> for <math>n</math> indexes.

Once we have the list we add push each element into a hash with a separate key for each word and update our estimate of the snippet <i>span</i> that includes all the words.

Here's python code for one simple implementation.

<pre>
import sys

def smallest_snippet(*args):
'''
args -- K lists of word positions for K words

>>> smallest_snippet([1,10], [2,20], [3,30])
[1, 3]
>>> smallest_snippet([1,9,27], [6,10,19], [8,12,14])
[8, 10]
>>> smallest_snippet([1,4,11,27], [3,6,10,19], [5,8,12,14])
[3, 5]
>>> smallest_snippet([1,4,5], [3,9,10], [2,6,15])
[1, 3]
'''

master = []
for i in range(len(args)):
master.extend(map(lambda j: (i,j), args[i])) # ith word, jth index
master.sort(lambda x,y: cmp(x[1], y[1])) # TODO: mergesort
tops = {} # { word i: index j }
best = [master[0][1], master[-1][1]]
minspan = best[-1] - best[0] + 1

# update span after each new index tuple
for (i,j) in master:
tops[i] = j
if len(tops) == len(args):
curr = [min(tops.values()), max(tops.values())]
if curr[1] - curr[0] < minspan:
minspan = curr[1] - curr[0]
best = curr

return best

if __name__ == "__main__":
import doctest
doctest.testmod()

sys.exit()
</pre>

@@ Line 6: / Line 6: @@
 Let's call the three lists of positions/indices A, B, and C.
-To begin, consider an abstract triplet &lt;A<sub>i</sub>, B<sub>j</sub>, C<sub>k</sub>&gt; where A<sub>i</sub> &lt; B<sub>j</sub> &lt; C<sub>k</sub>. For example, &lt;1, 6, 5&gt;.
+To begin, consider an abstract triplet &lt;A<sub>i</sub>, B<sub>j</sub>, C<sub>k</sub>&gt; where A<sub>i</sub> &lt; B<sub>j</sub> &lt; C<sub>k</sub>. For example, &lt;1, 3, 5&gt;.
 Incrementing j to j+1 can only result in an equally good (e.g., &lt;1, 4, 5&gt;) or worse (&lt;1, 6, 5&gt;) solution.

@@ Line 6: / Line 6: @@
 Let's call the three lists of positions/indices A, B, and C.
-To begin, consider an abstract triplet &lt;A<sub>i</sub>, B<sub>j</sub>, C<sub>k</sub>&gt; where A<sub>i</sub> &lt; B<sub>j</sub> &lt; C<sub>k</sub>. For example, &lt;1, 3, 5&gt;.
+To begin, consider an abstract triplet &lt;A<sub>i</sub>, B<sub>j</sub>, C<sub>k</sub>&gt; where A<sub>i</sub> &lt; B<sub>j</sub> &lt; C<sub>k</sub>. For example, &lt;1, 6, 5&gt;.
 Incrementing j to j+1 can only result in an equally good (e.g., &lt;1, 4, 5&gt;) or worse (&lt;1, 6, 5&gt;) solution.

@@ Line 1: / Line 1: @@
 Let's use the example given, for words say <i>A, B, C</i>,  in the problem but not get too tied to the specific values. It helps to think about sorting the search string words by their indexes in the document:
@@ Line 6: / Line 45: @@
 </pre>
-In the code example this is just a call to sort but since each word index list is sorted we could use <code>MergeSort</code> which means this portion of the code is <math>\mathcal{O}(n)</math> for <math>n</math> indexes.
+In the code example this is just a call to sort but since each word index list is sorted we could use <code>MergeSort</code> which means this portion of the code is <math>\mathcal{O}(n log(k))</math> for <math>n</math> indexes and <math>k</math> lists.
 Once we have the list we push each element into a hash with a separate key for each word and update our estimate of the snippet <i>span</i> that includes all the words.
@@ Line 56: / Line 95: @@
 ----

← Older revision		Revision as of 14:16, 15 July 2016
Line 54:		Line 54:
	sys.exit()		sys.exit()
	</source>		</source>
		+
		+	----
		+
		+
		+	Solution 2:
		+
		+	We can see from inspection that looking at pairwise combinations of indices tells us nothing. So we know 3 indices (one from each list) must be looked at in combination. We can also observe that the correct answer may involve indices at any position in the three lists (e.g., the solution may involve the final entry in each list).
		+
		+	Let's call the three lists of positions/indices A, B, and C.
		+
		+	To begin, consider an abstract triplet <A<sub>i</sub>, B<sub>j</sub>, C<sub>k</sub>> where A<sub>i</sub> < B<sub>j</sub> < C<sub>k</sub>. For example, <1, 3, 5>.
		+
		+	Incrementing j to j+1 can only result in an equally good (e.g., <1, 4, 5>) or worse (<1, 6, 5>) solution.
		+
		+	Similarly, incrementing k to k+1 can only result in a worse solution (e.g., <1, 3, 7>).
		+
		+	Therefore, incrementing i to i+1 provides the only possibility of finding a better solution (e.g., <2, 3, 5>), but may also produce a worse solution (<8, 3, 5>).
		+
		+	So, if we start with the triplet formed by the first element in each of the three lists, calculate the word span, and then loop by incrementing the index of the word position that occurs earliest in the text, we can proceed orderly though the lists of word positions, ignoring only combinations that are guaranteed not to produce a better solution.
		+
		+	Note that this approach also allows us to terminate the search early in the case where the triplet element representing the word with earliest occurrence in text (i.e., that which we would next increment) is the final entry in one of the word position lists (as we have shown above that all remaining unexplored combinations must have a greater span).
		+
		+	Applying this algorithm to the example given in the text results in combinations being tested in the following order:
		+
		+	<1, 3, 2>: 1-3<sup>*</sup>
		+	<4, 3, 2>: 2-4
		+	<4, 3, 6>: 3-6
		+	<4, 9, 6>: 4-9
		+	<5, 9, 6>: 6-9
		+
		+	The algorithm terminates here, as 5 is the lowest value and the word1 index list has no more elements).
		+
		+	The answer is the span 1-3, which we find by examining only 5 possible combinations.
		+
		+	The algorithm executes in linear time, O(n) = O(\|A\| + \|B\| + \|C\|), and can be easily extended to an arbitrary number of words.

@@ Line 12: / Line 12: @@
 Here's python code for one simple implementation.
-<pre>
+<source lang="python">
 import sys
@@ Line 53: / Line 53: @@
      sys.exit()
-</pre>
+</source>

@@ Line 1: / Line 1: @@
-Let's use the example given, for words say &lt;i&gt;A, B, C&lt;/i&gt;,  in the problem but not get too tied to the specific values. It helps to think about sorting the search string words by their indexes in the document:
+Let's use the example given, for words say <i>A, B, C</i>,  in the problem but not get too tied to the specific values. It helps to think about sorting the search string words by their indexes in the document:
-&lt;pre&gt;
+<pre>
 A  C  B  A  A  C  *  *  B  B  *  *  *  *  C
   2  3  4  5  6  7  8  9  10 11 12 13 14 15
-&lt;/pre&gt;
+</pre>
-In the code example this is just a call to sort but since each word index list is sorted we could use &lt;code&gt;MergeSort&lt;/code&gt; which means this portion of the code is &lt;math&gt;\mathcal{O}(n)&lt;/math&gt; for &lt;math&gt;n&lt;/math&gt; indexes.
+In the code example this is just a call to sort but since each word index list is sorted we could use <code>MergeSort</code> which means this portion of the code is <math>\mathcal{O}(n)</math> for <math>n</math> indexes.
-Once we have the list we add push each element into a hash with a separate key for each word and update our estimate of the snippet &lt;i&gt;span&lt;/i&gt; that includes all the words.
+Once we have the list we add push each element into a hash with a separate key for each word and update our estimate of the snippet <i>span</i> that includes all the words.
 Here's python code for one simple implementation.
-&lt;pre&gt;
+<pre>
 import sys
@@ Line 19: / Line 19: @@
      args -- K lists of word positions for K words
-     &gt;&gt;&gt; smallest_snippet([1,10], [2,20], [3,30])
+     >>> smallest_snippet([1,10], [2,20], [3,30])
      [1, 3]
-     &gt;&gt;&gt; smallest_snippet([1,9,27], [6,10,19], [8,12,14])
+     >>> smallest_snippet([1,9,27], [6,10,19], [8,12,14])
      [8, 10]
-     &gt;&gt;&gt; smallest_snippet([1,4,11,27], [3,6,10,19], [5,8,12,14])
+     >>> smallest_snippet([1,4,11,27], [3,6,10,19], [5,8,12,14])
      [3, 5]
-     &gt;&gt;&gt; smallest_snippet([1,4,5], [3,9,10], [2,6,15])
+     >>> smallest_snippet([1,4,5], [3,9,10], [2,6,15])
      [1, 3]
      '''
@@ Line 42: / Line 42: @@
          if len(tops) == len(args):
              curr = [min(tops.values()), max(tops.values())]
-             if curr[1] - curr[0] &lt; minspan:
+             if curr[1] - curr[0] < minspan:
                  minspan = curr[1] - curr[0]
                  best = curr
@@ Line 48: / Line 48: @@
      return best
-if __name__ == &quot;__main__&quot;:
+if __name__ == "__main__":
      import doctest
      doctest.testmod()
      sys.exit()
-&lt;/pre&gt;
+</pre>