{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"code","source":"!pip install cdifflib polyleven","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-07-30T08:21:39.789044Z","iopub.execute_input":"2022-07-30T08:21:39.789520Z","iopub.status.idle":"2022-07-30T08:21:51.588352Z","shell.execute_reply.started":"2022-07-30T08:21:39.789485Z","shell.execute_reply":"2022-07-30T08:21:51.587254Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"import numpy as np # linear algebra\nimport pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\nimport Levenshtein\nfrom unidecode import unidecode\nfrom tqdm import tqdm\nfrom polyleven import levenshtein\nimport time\n\nnames = pd.read_csv('../input/foursquare-location-matching/train.csv', usecols=['name'])\nnames = list(set(names.name.astype(str).apply(unidecode)))","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-07-30T08:21:51.590310Z","iopub.execute_input":"2022-07-30T08:21:51.590871Z","iopub.status.idle":"2022-07-30T08:22:01.133374Z","shell.execute_reply.started":"2022-07-30T08:21:51.590827Z","shell.execute_reply":"2022-07-30T08:22:01.132242Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# BK-Trees\n\nDuring this competition I came across an interesting type of data-structures. BK-Trees, proposed by Burkhard and Keller in 1973, can be used to find fuzzy matches between strings. They are commonly used for spell-checking. This notebook contains my implementation, a tree built from the column \"names\" from the competition data and some example queries.\n\n**Building the Tree**\n\nThe tree is built from a dictionary of words. The edge-weights contain the Levenshtein-Distances between the parent nodes and their children. Every node can have as many children as necessary, but only one child for each distance. We start building the tree by selecting a word for the root. From here we add words by calculating the distance between the root and the new word. We move down the tree if the current node already has child with the same distance. Otherwise, we add the word as a child to the root node. We repeat this process at every node we encounter until the word can be added as a child.\n\n**Finding Matches**\n\nTo find a close match to a string we first have to choose a threshold **t** for the maximum distance. Now we take the distance **d** between our string and the root node and query all children with an edge-weight between **d-t** and **d+t**. We continue this process for all relevant children and return the nodes where the distance between our string and the node is smaller or equal to the threshold.","metadata":{}},{"cell_type":"markdown","source":"# My Implementation","metadata":{}},{"cell_type":"code","source":"class Node:\n    \n    def __init__(self, word):\n        self.word = word\n        self.distances = []\n        self.children = []\n    \n    \nclass BKTree:\n    \n    def __init__(self):\n        self.root = None\n        \n    # builds tree from list of strings    \n    def build_tree(self, word_list):\n        self.root = Node(word_list.pop(0))\n        for word in tqdm(word_list):\n            self.add(word)\n    \n    # rfunction to add a word to the tree\n    def add(self, word):\n        \n        def add_child(node, word):\n            distance = levenshtein(node.word, word)\n            if distance in node.distances:\n                return add_child(node.children[node.distances.index(distance)], word)\n            node.distances.append(distance)\n            node.children.append(Node(word))\n              \n        add_child(self.root, word)\n\n    # finds close matches to a word where the distance is <= threshold\n    # returns a list of tuples (levenshtein-distance, word)\n    def find(self, word, threshold):\n        output_list = []\n        \n        candidates = [self.root]\n        \n        while len(candidates) > 0:\n            curr_candidate = candidates.pop(0)\n            curr_dist = levenshtein(curr_candidate.word, word)\n            if threshold >= curr_dist:\n                output_list.append((curr_dist, curr_candidate.word))\n            candidates.extend(child for distance, child in zip(curr_candidate.distances, curr_candidate.children) \n                              if curr_dist - threshold <= distance <= curr_dist + threshold)\n            \n        return output_list","metadata":{"execution":{"iopub.status.busy":"2022-07-30T08:22:01.134960Z","iopub.execute_input":"2022-07-30T08:22:01.135329Z","iopub.status.idle":"2022-07-30T08:22:01.205840Z","shell.execute_reply.started":"2022-07-30T08:22:01.135298Z","shell.execute_reply":"2022-07-30T08:22:01.204339Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"bk_tree = BKTree()\nbk_tree.build_tree(names)","metadata":{"execution":{"iopub.status.busy":"2022-07-30T08:22:01.209767Z","iopub.execute_input":"2022-07-30T08:22:01.210305Z","iopub.status.idle":"2022-07-30T08:22:21.921594Z","shell.execute_reply.started":"2022-07-30T08:22:01.210257Z","shell.execute_reply":"2022-07-30T08:22:21.920160Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Querying Some Examples\n\nThe following section shows the results for 10 names at a threshold of 2.","metadata":{}},{"cell_type":"code","source":"sample = ['Gimnaziia 291', 'Room 71', 'The Balat', \n          'Adidas', 'Starbucks', '7-Eleven', \n          '`aakhaar 2 ptibatikaarwiswkrrmsaastr (Building 2)',\n          'Balci Apartmani', 'Divan Hotel', \"Nell's\"]\n\nresults = {}\n\nfor s in tqdm(sample):\n    results[s] = bk_tree.find(s, 2)","metadata":{"execution":{"iopub.status.busy":"2022-07-30T08:22:21.922901Z","iopub.execute_input":"2022-07-30T08:22:21.923241Z","iopub.status.idle":"2022-07-30T08:22:23.588553Z","shell.execute_reply.started":"2022-07-30T08:22:21.923212Z","shell.execute_reply":"2022-07-30T08:22:23.587223Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(results['Gimnaziia 291'])","metadata":{"execution":{"iopub.status.busy":"2022-07-30T08:22:23.590583Z","iopub.execute_input":"2022-07-30T08:22:23.591145Z","iopub.status.idle":"2022-07-30T08:22:23.598714Z","shell.execute_reply.started":"2022-07-30T08:22:23.591081Z","shell.execute_reply":"2022-07-30T08:22:23.597147Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(results['Room 71'])","metadata":{"execution":{"iopub.status.busy":"2022-07-30T08:22:23.600961Z","iopub.execute_input":"2022-07-30T08:22:23.601454Z","iopub.status.idle":"2022-07-30T08:22:23.613865Z","shell.execute_reply.started":"2022-07-30T08:22:23.601409Z","shell.execute_reply":"2022-07-30T08:22:23.612436Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(results['The Balat'])","metadata":{"execution":{"iopub.status.busy":"2022-07-30T08:22:23.615502Z","iopub.execute_input":"2022-07-30T08:22:23.616010Z","iopub.status.idle":"2022-07-30T08:22:23.627829Z","shell.execute_reply.started":"2022-07-30T08:22:23.615960Z","shell.execute_reply":"2022-07-30T08:22:23.626225Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(results['Adidas'])","metadata":{"execution":{"iopub.status.busy":"2022-07-30T08:22:23.629658Z","iopub.execute_input":"2022-07-30T08:22:23.630167Z","iopub.status.idle":"2022-07-30T08:22:23.640545Z","shell.execute_reply.started":"2022-07-30T08:22:23.630097Z","shell.execute_reply":"2022-07-30T08:22:23.639210Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(results['Starbucks'])","metadata":{"execution":{"iopub.status.busy":"2022-07-30T08:22:23.645580Z","iopub.execute_input":"2022-07-30T08:22:23.646015Z","iopub.status.idle":"2022-07-30T08:22:23.656298Z","shell.execute_reply.started":"2022-07-30T08:22:23.645980Z","shell.execute_reply":"2022-07-30T08:22:23.654766Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(results['7-Eleven'])","metadata":{"execution":{"iopub.status.busy":"2022-07-30T08:22:23.657997Z","iopub.execute_input":"2022-07-30T08:22:23.658739Z","iopub.status.idle":"2022-07-30T08:22:23.668529Z","shell.execute_reply.started":"2022-07-30T08:22:23.658689Z","shell.execute_reply":"2022-07-30T08:22:23.667131Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(results['`aakhaar 2 ptibatikaarwiswkrrmsaastr (Building 2)'])","metadata":{"execution":{"iopub.status.busy":"2022-07-30T08:22:23.670973Z","iopub.execute_input":"2022-07-30T08:22:23.671427Z","iopub.status.idle":"2022-07-30T08:22:23.685201Z","shell.execute_reply.started":"2022-07-30T08:22:23.671393Z","shell.execute_reply":"2022-07-30T08:22:23.683993Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(results['Balci Apartmani'])","metadata":{"execution":{"iopub.status.busy":"2022-07-30T08:22:23.687335Z","iopub.execute_input":"2022-07-30T08:22:23.687786Z","iopub.status.idle":"2022-07-30T08:22:23.697914Z","shell.execute_reply.started":"2022-07-30T08:22:23.687750Z","shell.execute_reply":"2022-07-30T08:22:23.695887Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(results['Divan Hotel'])","metadata":{"execution":{"iopub.status.busy":"2022-07-30T08:22:23.699943Z","iopub.execute_input":"2022-07-30T08:22:23.700917Z","iopub.status.idle":"2022-07-30T08:22:23.711762Z","shell.execute_reply.started":"2022-07-30T08:22:23.700873Z","shell.execute_reply":"2022-07-30T08:22:23.710430Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(results[\"Nell's\"])","metadata":{"execution":{"iopub.status.busy":"2022-07-30T08:22:23.712797Z","iopub.execute_input":"2022-07-30T08:22:23.713176Z","iopub.status.idle":"2022-07-30T08:22:23.723858Z","shell.execute_reply.started":"2022-07-30T08:22:23.713134Z","shell.execute_reply":"2022-07-30T08:22:23.721929Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# References\n\n* https://dl.acm.org/doi/abs/10.1145/362003.362025\n* https://medium.com/future-vision/bk-trees-unexplored-data-structure-ec234f39052d\n* https://www.youtube.com/watch?v=b2xALzFPwGA","metadata":{}}]}