<jupyter_start><jupyter_text>Spell Checker Edit 1: Stupid Naive approach (Code deleted, it was just looping over everything maybe will take one year to solve this problem) Edit 2: <NAME>'s spell checker Edit 3: Added Trie<jupyter_code># This Python 3 environment comes with many helpful analytics libraries installed
# It is defined by the kaggle/python docker image: https://github.com/kaggle/docker-python
# For example, here's several helpful packages to load in 

import numpy as np # linear algebra
import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)

# Input data files are available in the "../input/" directory.
# For example, running this (by clicking run or pressing Shift+Enter) will list all files under the input directory

import os
for dirname, _, filenames in os.walk('/kaggle/input'):
    for filename in filenames:
        print(os.path.join(dirname, filename))

# Any results you write to the current directory are saved as output.
# Required Distance
!pip install textdistance
import textdistance
import time
import csv
import tqdm
import operator

word_file = '/kaggle/input/itmo-spelling-correction-autumn-2019/words.csv'
train_file = '/kaggle/input/itmo-spelling-correction-autumn-2019/no_fix.submission.csv'
truth_file = '/kaggle/input/itmo-spelling-correction-autumn-2019/train.csv'
# Load Word Dict
words = {}

with open(word_file, newline='') as file:
    buffer = csv.DictReader(file)
    for r in tqdm.tqdm(buffer):
        words[r['Id']] = int(r['Freq'])
# Load Truth File
truth_values = set()

with open(truth_file, newline='') as file:
    buffer = csv.DictReader(file)
    for r in tqdm.tqdm(buffer):
        truth_values.add(r['Expected'])

len(truth_values)
distance_to_keep = [1, 2]
distance_function = textdistance.levenshtein
WORDS = words

def correction(initial_word, threshold=1000):
    "Most probable spelling correction for word."
    probability_dict = {}
    # Probability for just the word
    for word in known([initial_word]):
        if word in WORDS:
            if WORDS[word] > threshold:
                probability_dict[word] = WORDS[word]
        
    
    # Probability for one edit
    for word in known(edits1(initial_word)):
        if word in WORDS:
            if WORDS[word] > threshold:
                probability_dict[word] = WORDS[word]
    
#     # Probability for two edits
#     for word in known(edits2(word)):
#         probability_dict[word] = WORDS[word]
#     print(f'Prob dictionary: {probability_dict}')

    if probability_dict:
        correction = sorted(probability_dict.items(), key=operator.itemgetter(1), reverse=True)[0][0]
    else:
        correction = initial_word

    return correction


def known(words):
    "The subset of `words` that appear in the dictionary of WORDS."
    if words:
        return set(w for w in words if w and w in truth_values)
    return set()

        

def edits1(word):
    "All edits that are one edit away from `word`."
    letters    = 'бвгджзклмнпрстфхцчшщаэыуояеёюийьъabcdefghijklmnopqrstuvwxyz'.upper()
    splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]
    deletes    = [L + R[1:]               for L, R in splits if R]
    transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
    replaces   = [L + c + R[1:]           for L, R in splits if R for c in letters]
    inserts    = [L + c + R               for L, R in splits for c in letters]
    return set(deletes + transposes + replaces + inserts)

def edits2(word): 
    "All edits that are two edits away from `word`."
    return (e2 for e1 in edits1(word) for e2 in edits1(e1))
correction('АНІМЕ')
correction('UNIZOOI')<jupyter_output><empty_output><jupyter_text>Testing This It works lets try on all test set<jupyter_code>train = []
with open(train_file) as file:
    buffer = csv.DictReader(file)
    for r in tqdm.tqdm(buffer):
        train.append(r['Id'])
with open('submission_pn.csv', 'w', newline='') as file:
    buffer = csv.writer(file)
    buffer.writerow(['Id', 'Predicted'])
    for word in tqdm.tqdm(train):
        corr = correction(word, 4000)
        buffer.writerow([word, corr])<jupyter_output>100%|██████████| 362256/362256 [03:56<00:00, 1529.04it/s]<jupyter_text>**Trie**<jupyter_code>"""
My just Trie Implementation: https://github.com/shivammehta007/pythondsa/blob/master/structures/trie.py
This is just addon to the normal Trie
"""

class Trie:
    """
    Trie

    Trie is a treelike datastructure used to predict suggestion here is a
    simple implementation of it with add and search functionality.

    It has a root that is the head or the Trie and a node_count to count
    total number of nodes currently in Trie
    """

    class _Node:
        """
        Node

        This is how a trie node looks like it has a hashmap of characters
        with an end indicating weather this is the end of word or not.
        One additional field that I added is the frequency count just for
        furthur probabilistic calculations if required.
        """

        def __init__(self, end=False):
            self.characters = {}
            self.frequency = 0
            self.end = end

    def __init__(self):
        self.root = self._Node()
        self.node_count = 1


    def add_string(self, string):
        """
        Adds a string to the trie
        Parameters:
        string: String
        """
        node = self.root
        for c in string:
            if c not in node.characters:
                node.characters[c] = self._Node()
                self.node_count += 1

            node = node.characters[c]

        node.end = True
        if string in WORDS:
            node.frequency = WORDS[string]

    def search_word(self, string):
        """
        Searches for a word in the trie
        Parameters:
        string: String
        """
        node = self.root
        for c in string:
            if c not in node.characters:
                return False, 0
            node = node.characters[c]

        if node.end:
            return True, node.frequency

        return False, 0

    def one_edit_distance(self, word):
        """
        All edits that are one edit away from word
        Parameters:
        word: String
        """
        
        letters    = 'бвгджзклмнпрстфхцчшщаэыуояеёюийьъabcdefghijklmnopqrstuvwxyz'.upper()
        splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]
        deletes    = [L + R[1:]               for L, R in splits if R]
        transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
        replaces   = [L + c + R[1:]           for L, R in splits if R for c in letters]
        inserts    = [L + c + R               for L, R in splits for c in letters]
        return set(deletes + transposes + replaces + inserts)
    
    
    def correct_spelling(self, initial_word, threshold=1000):
        """
        Checks and Returns the Correct Spelling of the Word with one edit distance
        """
        probability_dict = {}
        present, _ = self.search_word(initial_word)
        if present:
            return initial_word
    
        for word in self.one_edit_distance(initial_word):
            present, freq = self.search_word(word)
            if not present:
                continue
            probability_dict[word] = freq
            

        if probability_dict:
            correction = sorted(probability_dict.items(), key=operator.itemgetter(1), reverse=True)[0][0]
        else:
            correction = initial_word
        
        return correction
  
trie = Trie()
for word in tqdm.tqdm(truth_values):
    trie.add_string(word)<jupyter_output>100%|██████████| 332090/332090 [00:13<00:00, 24794.82it/s]<jupyter_text>Some Tests<jupyter_code>trie.search_word('АНИМЕ')
trie.correct_spelling('КИТАЦ') # КИТАЙ<jupyter_output><empty_output><jupyter_text>Lets Create the final Submission<jupyter_code>with open('submission_trie.csv', 'w', newline='') as file:
    buffer = csv.writer(file)
    buffer.writerow(['Id', 'Predicted'])
    for word in tqdm.tqdm(train):
        corr = trie.correct_spelling(word)
        buffer.writerow([word, corr])<jupyter_output>100%|██████████| 362256/362256 [15:42<00:00, 384.37it/s]
{'fraction_non_alphanumeric': 0.10396883369856343, 'fraction_numerical': 0.018870221572924277, 'mean_word_length': 2.598335523434078, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 23, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '467570', 'license': 'MIT', 'n_tokens_mistral': 2804, 'n_tokens_neox': 2613, 'n_words': 793, 'path': 'Attempt3_Trie_and_Peter Norvig.ipynb', 'repo_name': 'shivammehta007/Information-Retrieval', 'size': '8221'}