<jupyter_start><jupyter_text>HW1: Dictionary-based Tokenization  In this exercise, you are to implement a dictionary-based word segmentation algorithm. There are two Python functions that you need to complete: * maximal_matching* backtrack  Create a toy dictionary to test the algorithmThis is based on the example shown in the lecture. You will tokenize the following text string: "ไปหามเหสี!"The toy dictoionary provided in this exercise includes all the charaters, syllables, and words that appear that the text string.<jupyter_code>thai_vocab = ["ไ","ป","ห","า","ม","เ","ห","ส","ี","ไป","หา","หาม","เห","สี","มเหสี","!"]<jupyter_output><empty_output><jupyter_text>Maximal matching Complete the maximal matching  function below to tokenize the input text<jupyter_code>from math import inf #infinity
def maximal_matching(c):
	#Initialize an empty 2D list
	d  =[[None]*len(c) for _ in range(len(c))]
	
	for i in range(len(c)):
		for j in range(i, len(c)):
			if i == 0 and j == 0:
				d[i][j] = 1
				continue
			consideredWord = c[i:j+1]
			if consideredWord in thai_vocab:
				print(consideredWord+"\n")
				d[i][j] = 1
				if i == 0:
					continue
				min = inf
				for k in range(i):
					if d[k][i-1] < min:
						min = d[k][i-1]
				if min != inf:
					d[i][j] = d[i][j] + min
				else:
					d[i][j] = inf
			else:
				d[i][j] = inf






	
	######################
	
	return d<jupyter_output><empty_output><jupyter_text>BacktrackingComplete the backtracking function below to find the tokenzied words.It should return a list containing a pair of the beginning position and the ending position of each word.In this example, it should return: [(0, 1),(2, 3),(4, 8),(9, 9)]  Each pair contains the position of each word as follows:(0, 1) ไป(2, 3) หา(4, 8) มเหสี(9, 9) !<jupyter_code>def backtrack(d):
	eow = len(d)-1 # End of Word position
	word_pos = [] # Word position

	currentEnd = eow
	currentStart = eow
	#print((currentStart, currentEnd))
	while(currentEnd >= 0):
		#print((currentStart, currentEnd))
		currentMin = d[currentEnd][currentEnd]
		for j in range(currentEnd, -1, -1):
			if d[j][currentEnd] < currentMin:
				currentMin = d[j][currentEnd]
				currentStart = j
		word_pos.append((currentStart, currentEnd))
		currentEnd = currentStart - 1
	word_pos.reverse()
	return word_pos<jupyter_output><empty_output><jupyter_text>Test your maximal matching algorithm on a toy dictionaryExpected output:[1, 1, inf, inf, inf, inf, inf, inf, inf, inf] ไ[None, 2, inf, inf, inf, inf, inf, inf, inf, inf] ป[None, None, 2, 2, 2, inf, inf, inf, inf, inf] ห[None, None, None, 3, inf, inf, inf, inf, inf, inf] า[None, None, None, None, 3, inf, inf, inf, 3, inf] ม[None, None, None, None, None, 3, 3, inf, inf, inf] เ[None, None, None, None, None, None, 4, inf, inf, inf] ห[None, None, None, None, None, None, None, 4, 4, inf] ส[None, None, None, None, None, None, None, None, 5, inf] ี[None, None, None, None, None, None, None, None, None, 4] !<jupyter_code>input_text = "ไปหามเหสี!"
out = maximal_matching(input_text)
for i in range(len(out)):
    print(out[i],input_text[i])<jupyter_output>ไป

ป

ห

หา

หาม

า

ม

มเหสี

เ

เห

ห

ส

สี

ี

!

[1, 1, inf, inf, inf, inf, inf, inf, inf, inf] ไ
[None, 2, inf, inf, inf, inf, inf, inf, inf, inf] ป
[None, None, 2, 2, 2, inf, inf, inf, inf, inf] ห
[None, None, None, 3, inf, inf, inf, inf, inf, inf] า
[None, None, None, None, 3, inf, inf, inf, 3, inf] ม
[None, None, None, None, None, 3, 3, inf, inf, inf] เ
[None, None, None, None, None, None, 4, inf, inf, inf] ห
[None, None, None, None, None, None, None, 4, 4, inf] ส
[None, None, None, None, None, None, None, None, 5, inf] ี
[None, None, None, None, None, None, None, None, None, 4] !<jupyter_text>Test your backtracking algorithm on a toy dictionaryExpected output:ไป|หา|มเหสี|!<jupyter_code>def print_tokenized_text(d, input_text):
    tokenized_text=[]
    for pos in backtrack(d):
        print(pos)
        tokenized_text.append(input_text[pos[0]:pos[1]+1])

    print("|".join(tokenized_text))
    
print_tokenized_text(out,input_text)<jupyter_output>(0, 1)
(2, 3)
(4, 8)
(9, 9)
ไป|หา|มเหสี|!<jupyter_text>Now try it on a real dictionary For UNIX-based OS users, the following cell will download a dictionary (it's just a list of thai words). Alternatively, you can download it from this link: https://raw.githubusercontent.com/PyThaiNLP/pythainlp/dev/pythainlp/corpus/words_th.txt<jupyter_code>!wget https://raw.githubusercontent.com/PyThaiNLP/pythainlp/dev/pythainlp/corpus/words_th.txt
with open("words_th.txt",encoding='utf-8-sig') as f:
    thai_vocab = f.read().splitlines() 
print("Vocab size:", len(thai_vocab))
print(thai_vocab[:10])
#you can add more vocab to the dictionary 
thai_vocab.extend(["ๆ","!"])<jupyter_output>Vocab size: 63529
['ก.', 'ก.ค.', 'ก.ต.', 'ก.ป.ส.', 'ก.พ.', 'ก.พ.ด.', 'ก.ม.', 'ก.ย', 'ก.ย.', 'ก.ร.']<jupyter_text>The output of your maximal matching algoithm on a new dictionaryExpected output:[1, 1, inf, 1, inf, inf, inf, inf, inf] ไ[None, 2, inf, inf, inf, inf, inf, inf, inf] ป[None, None, 2, 2, 2, inf, inf, inf, inf] ห[None, None, None, inf, inf, inf, inf, inf, inf] า[None, None, None, None, 2, inf, inf, inf, 2] ม[None, None, None, None, None, inf, 3, inf, inf] เ[None, None, None, None, None, None, inf, inf, inf] ห[None, None, None, None, None, None, None, 4, 4] ส[None, None, None, None, None, None, None, None, None] ี<jupyter_code>input_text = "ไปหามเหสี"
out = maximal_matching(input_text)
for i in range(len(out)):
    print(out[i],input_text[i])<jupyter_output>ไป

ไปหา

ป

ห

หา

หาม

ม

มเหสี

เห

ห

ส

สี

[1, 1, inf, 1, inf, inf, inf, inf, inf] ไ
[None, 2, inf, inf, inf, inf, inf, inf, inf] ป
[None, None, 2, 2, 2, inf, inf, inf, inf] ห
[None, None, None, inf, inf, inf, inf, inf, inf] า
[None, None, None, None, 2, inf, inf, inf, 2] ม
[None, None, None, None, None, inf, 3, inf, inf] เ
[None, None, None, None, None, None, inf, inf, inf] ห
[None, None, None, None, None, None, None, 4, 4] ส
[None, None, None, None, None, None, None, None, inf] ี<jupyter_text>Expected tokenized textไปหา|มเหสี<jupyter_code>print_tokenized_text(out,input_text)<jupyter_output>(0, 3)
(4, 8)
ไปหา|มเหสี
{'fraction_non_alphanumeric': 0.16314248536109305, 'fraction_numerical': 0.017891997397527653, 'mean_word_length': 4.559674502712477, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 29, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '205381', 'license': 'Apache-2.0', 'n_tokens_mistral': 2660, 'n_tokens_neox': 2489, 'n_words': 793, 'path': 'HW1/hw1_dictionary_based_tokenization.ipynb', 'repo_name': 'pawin35/NLP_2019_coursework', 'size': '6148'}