TADM2E 3.29 - Revision history

Matt: Undo revision 1066 by FuckMatt (talk)

2020-08-01T01:00:21Z

Undo revision 1066 by FuckMatt (talk)

FuckMatt: Blanked the page

2020-07-31T09:38:30Z

Blanked the page

Matt: Undo revision 789 by EthanGamer (talk)

2020-07-23T13:38:14Z

Undo revision 789 by EthanGamer (talk)

EthanGamer: Replaced content with " Tus"

2020-07-14T01:57:36Z

Replaced content with " Tus"

MagalooXX: added solution using Trie

2014-10-06T07:50:41Z

added solution using Trie

Algowikiadmin: Recovering wiki

2014-09-11T18:13:10Z

Recovering wiki

New page

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)

← Older revision	Revision as of 01:00, 1 August 2020
Line 1:	Line 1:

	+	== 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 <math>O(n)</math> if the hashtable contains <math>m=n</math> slots (in general, lookup in a hashtable takes <math>O(n/m)</math> time). Still, this approach could work well if <math>m</math> 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 <math>O(n)</math> time), using two word pointers <code>word1</code> and <code>word2</code> 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 <math>m</math> in the example using the hashtable).
	+
	+	<source lang="python">
	+
	+	class Trie:
	+
	+	def __init__(self, parent=None):
	+	self.parent = parent
	+	self.children = {}
	+	self.n = 0
	+
	+	def add(self, c):
	+	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
	+	word2 = word1.add(' ')
	+	word1 = root
	+	else:
	+	word1 = root
	+	word2 = word2.add(' ')
	+	else:
	+	word2 = word2.add(c)
	+	if word1:
	+	word1 = word1.add(c)
	+	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:
	+	word, n = pairmax(urllib2.urlopen(url).read())
	+	sys.stdout.write('%s : %dx "%s"\n' %(url, n, word))
	+	</source>

← Older revision		Revision as of 09:38, 31 July 2020
Line 1:		Line 1:

−	~~== 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 <math>O(n)</math> if the hashtable contains <math>m=n</math> slots (in general, lookup in a hashtable takes <math>O(n/m)</math> time). Still, this approach could work well if <math>m</math> 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 <math>O(n)</math> time), using two word pointers <code>word1</code> and <code>word2</code> 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 <math>m</math> in the example using the hashtable).
−
−	~~<source lang="python">~~
−
−	~~class Trie:~~
−
−	~~def __init__(self, parent=None):~~
−	~~self.parent = parent~~
−	~~self.children = {}~~
−	~~self.n = 0~~
−
−	~~def add(self, c):~~
−	~~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~~
−	~~word2 = word1.add(' ')~~
−	~~word1 = root~~
−	~~else:~~
−	~~word1 = root~~
−	~~word2 = word2.add(' ')~~
−	~~else:~~
−	~~word2 = word2.add(c)~~
−	~~if word1:~~
−	~~word1 = word1.add(c)~~
−	~~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:~~
−	~~word, n = pairmax(urllib2.urlopen(url).read())~~
−	~~sys.stdout.write('%s : %dx "%s"\n' %(url, n, word))~~
−	~~</source>~~

← Older revision		Revision as of 13:38, 23 July 2020
Line 1:		Line 1:

−	~~Tus~~	+	== 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 <math>O(n)</math> if the hashtable contains <math>m=n</math> slots (in general, lookup in a hashtable takes <math>O(n/m)</math> time). Still, this approach could work well if <math>m</math> 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 <math>O(n)</math> time), using two word pointers <code>word1</code> and <code>word2</code> 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 <math>m</math> in the example using the hashtable).
		+
		+	<source lang="python">
		+
		+	class Trie:
		+
		+	def __init__(self, parent=None):
		+	self.parent = parent
		+	self.children = {}
		+	self.n = 0
		+
		+	def add(self, c):
		+	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
		+	word2 = word1.add(' ')
		+	word1 = root
		+	else:
		+	word1 = root
		+	word2 = word2.add(' ')
		+	else:
		+	word2 = word2.add(c)
		+	if word1:
		+	word1 = word1.add(c)
		+	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:
		+	word, n = pairmax(urllib2.urlopen(url).read())
		+	sys.stdout.write('%s : %dx "%s"\n' %(url, n, word))
		+	</source>

← Older revision		Revision as of 01:57, 14 July 2020
Line 1:		Line 1:

−	~~== Using a Hashtable ==~~	+	Tus
−
−	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 <math>O(n)</math> if the hashtable contains <math>m=n</math> slots (in general, lookup in a hashtable takes <math>O(n/m)</math> time). Still, this approach could work well if <math>m</math> 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 <math>O(n)</math> time), using two word pointers <code>word1</code> and <code>word2</code> 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 <math>m</math> in the example using the hashtable).
−
−	~~<source lang="python">~~
−
−	~~class Trie:~~
−
−	~~def __init__(self, parent=None):~~
−	~~self.parent = parent~~
−	~~self.children = {}~~
−	~~self.n = 0~~
−
−	~~def add(self, c):~~
−	~~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~~
−	~~word2 = word1.add(' ')~~
−	~~word1 = root~~
−	~~else:~~
−	~~word1 = root~~
−	~~word2 = word2.add(' ')~~
−	~~else:~~
−	~~word2 = word2.add(c)~~
−	~~if word1:~~
−	~~word1 = word1.add(c)~~
−	~~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:~~
−	~~word, n = pairmax(urllib2.urlopen(url).read())~~
−	~~sys.stdout.write('%s : %dx "%s"\n' %(url, n, word))~~
−	~~</source>~~

← Older revision		Revision as of 07:50, 6 October 2014
Line 1:		Line 1:
		+
		+	== 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.		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.

Line 6:		Line 9:

	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)		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 <math>O(n)</math> if the hashtable contains <math>m=n</math> slots (in general, lookup in a hashtable takes <math>O(n/m)</math> time). Still, this approach could work well if <math>m</math> 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 <math>O(n)</math> time), using two word pointers <code>word1</code> and <code>word2</code> 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 <math>m</math> in the example using the hashtable).
		+
		+	<source lang="python">
		+
		+	class Trie:
		+
		+	def __init__(self, parent=None):
		+	self.parent = parent
		+	self.children = {}
		+	self.n = 0
		+
		+	def add(self, c):
		+	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
		+	word2 = word1.add(' ')
		+	word1 = root
		+	else:
		+	word1 = root
		+	word2 = word2.add(' ')
		+	else:
		+	word2 = word2.add(c)
		+	if word1:
		+	word1 = word1.add(c)
		+	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:
		+	word, n = pairmax(urllib2.urlopen(url).read())
		+	sys.stdout.write('%s : %dx "%s"\n' %(url, n, word))
		+	</source>