# 3.45

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Using a Hashtable

Scan the web page word by word and for each one, except the first, take the pair formed by the previous word + the current one. Use that pair as the key to a hashtable, where you store the frequency of that pair. If the entry is not already in the hash table store it with value 1, if it is there increment the current value by one. Keep the highest frequency seen and update it wherever you see a greater one. In the end return the greatest frequency seen.

Complexity, where N = number of words in the text:

Time: O(N) (you only iterate over each word once)

Space: O(N) (Worst case is when every word is distinct and thus you have no repeated pairs, and that would take N storage on the hash table)

## Using a Trie

The solution with the hashtable will only work in time ${\displaystyle O(n)}$ if the hashtable contains ${\displaystyle m=n}$ slots (in general, lookup in a hashtable takes ${\displaystyle O(n/m)}$ time). Still, this approach could work well if ${\displaystyle m}$ is chosen wisely.

Another approach would be to store the text in a trie and save the number of occurrences in the leaf nodes. The implementation below iterates through the text letter by letter (in ${\displaystyle O(n)}$ time), using two word pointers `word1` and `word2` that point to the position in the trie of the current word and the concatenation of the current with the last word, respectively.

If the text is long and natural, it is expected to contain many repetitions and common prefixes, and an efficient implementation would use relatively little memory. Another advantage is that no parameters have to be pre-defined (such as ${\displaystyle m}$ in the example using the hashtable).

```class Trie:

def __init__(self, parent=None):
self.parent = parent
self.children = {}
self.n = 0

return self.children.setdefault(c, Trie(self))

def letter(self, child):
for c in self.children:
if self.children[c] == child:
return c
return None

def spell(self):
if self.parent:
return self.parent.spell() + self.parent.letter(self)
return ''

def wrap(text):
"""iterates through text, yielding lowercase letter or single ' '"""
inword = False
for c in text:
c = c.lower()
if ord(c) >= ord('a') and ord(c) <= ord('z'):
yield c
inword = True
else:
if inword:
yield ' '
inword = False
if inword:
yield ' '

def pairmax(text):
"""finds the word pair with maximum occurrence"""
root = word2 = Trie()
best = word1 = None
for c in wrap(text):
if c == ' ':
if word1:
word2.n += 1
if best is None or word2.n > best.n:
best = word2
word1 = root
else:
word1 = root
else:
if word1:
return best.spell(), best.n

if __name__ == '__main__':
import urllib2, sys

urls = sys.argv[1:]
if not urls:
urls = ['http://www.rfc-editor.org/rfc/rfc19%02d.txt' % i for i in range(30, 40)]

for url in urls:
sys.stdout.write('%s : %dx "%s"\n' %(url, n, word))```

Back to Chapter 3