# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # Our Task: Find similar company names
#
#

# Now that we have completed our Python Primer, let's try to complete a real task, while at the same time trying to practice loops, iterations, and other Python functionality that we studied.

# ## Your high level task
#
#

# You are given a list of names. You know that the same entity in the list has different representations. You want to find duplicate companies in the data.
#
# As a concrete example, open the file under `data/restaurant-names.txt`. This contains a list of restaurant names, extracted from the [NYC Restaurant inspection data set](https://data.cityofnewyork.us/Health/DOHMH-New-York-City-Restaurant-Inspection-Results/xx67-kt59/data) (available online). The Department of Health has been doing a decent, but not perfect, job in recording the company names. Therefore, the same restaurant appears under different names. **Your task is to find "almost duplicate" entries in order to decide whether they correspond to the same business.**
#

# !head -10 ../data/restaurant-names.txt

# !tail -5 ../data/restaurant-names.txt

# ## Matching Company Names

# Quite often, in our data, we have entries represented as strings that refer to the same entity but have different string representations (e.g., McDonald's vs McDonalds vs McDonald‎). We want to write code that will help in the task of finding such similar entries in our data.
#
# Our task can be broken in the following tasks:
# * **Step 1**: Read the data from a file into a list of strings in memory. We have a data set under the `data` folder: The list of unique restaurant names from the NYC Restaurant Inspection dataset (`data/restaurant-names.txt`). We need to write Python code that will read th file and return a list of strings that are the company names.
# * **Step 2**: We will then need to figure out how to compare two strings and find their similarity. For that, we will write a function that takes as input **two** strings, and returns back their similarities. We will explore multiple ways of writing that function, using various library functions.
# * **Step 3**: We will need to write a function that takes as input a company name, and returns back a list of matching company names, together with their similarity. Ideally, we would like to also sort the list based on the similarity (highest similarity metrics on top). As part of our learning process, we will use the _list comprehension_ approach to create the list. We will also use tuples as the elements of the list, so that the list contain elements such as `[("McDonalds", 0.88), ("McDonald's", 0.81),....]`.
# * **Step 4**: In the final step, we will just perform the similarity computation across all companies in the dataset.

# ## STEP 1: Read the list of names from a file and create a list of names

# +
# STEP 1: Read the list of names from a file and create a list of names
filename = '../data/restaurant-names.txt'

# We open the filename for reading
f = ...
# Read the file into memory
content = ...
# Content is a big string, with one restaurant per line
# so we split it into lines and create a list with the restaurant names
restaurants = ...

# + [markdown] solution2="hidden" solution2_first=true
# ### Solution

# + solution2="hidden"
# STEP 1: Read the list of names from a file and create a list of names
filename = '../data/restaurant-names.txt'

# We open the filename for reading
f = open(filename, 'r')
# Read the file into memory
content = f.read()
# Content is a big string, with one restaurant per line
# so we split it into lines and create a list with the restaurant names
restaurants = content.split('\n')

# + solution2="hidden"
len(restaurants)

# + solution2="hidden"
restaurants
# -

# ## STEP 2: Implement the similarity function

# ### Computing the similarity between two strings

# There are many ways that we can calculate the similarity between two strings. For our case, we will focus on a few similarity metrics that already have implementations in Python. 
#
# #### Some commonly used similarity metrics
#
# * [Sequence matching](https://docs.python.org/3.6/library/difflib.html) (part of standard Python) ([example](http://stackoverflow.com/questions/17388213/find-the-similarity-percent-between-two-strings))
# * [Edit distance](https://en.wikipedia.org/wiki/Edit_distance) ([Python Jellyfish Library](https://github.com/jamesturk/jellyfish))
# * [N-gram distance](http://pythonhosted.org/ngram/tutorial.html#comparing-and-searching-strings)
#
#
# #### STEP 2.a: Let's install the libraries...

# Edit distance
# !sudo -H pip3 install -U jellyfish

# Ngram
# !sudo -H pip3 install -U ngram

# #### STEP 2.b: Now let's test our similarity functions with various examples
#
# Once we have installed the necessary libraries for our project, we proceed to `import` them and test the functions.

import jellyfish

# ##### Edit Distance
#
# From Wikipedia:
#
# The [edit distance](https://en.wikipedia.org/wiki/Edit_distance) _ is a way of quantifying how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other._. 
#
# The Levenshtein distance between "kitten" and "sitting" is 3. A minimal edit script that transforms the former into the latter is:
#
# * kitten → sitten (substitution of "s" for "k")
# * sitten → sittin (substitution of "i" for "e")
# * sittin → sitting (insertion of "g" at the end).

jellyfish.levenshtein_distance('kitten', 'sitting')

# Let's try a few more examples

jellyfish.levenshtein_distance('Ipeirotis', 'Iperiotos')

jellyfish.levenshtein_distance('Starbucks', 'Starbacks')

jellyfish.levenshtein_distance('Starbucks', 'Starbuck')

jellyfish.levenshtein_distance('Starbucks', 'Wendys')

# ##### Demerau Levenshtein distance
#
# The Demerau Levenshtein distance also allows for  transposition of two adjacent characters.

jellyfish.levenshtein_distance('Ipeirotis', 'Iperiotis')

jellyfish.damerau_levenshtein_distance('Ipeirotis', 'Iperiotis')

jellyfish.damerau_levenshtein_distance('Starbucks', 'Starbucsk')

jellyfish.levenshtein_distance('Starbucks', 'Starbucsk')

# ###### Jaro–Winkler distance
#
# [Jaro–Winkler distance](https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance) is a string metric for measuring the edit distance between two sequences. Informally, the **Jaro** distance between two words is the minimum number of single-character transpositions required to change one word into the other; the **Jaro–Winkler** distance  gives more favourable ratings to strings that match from the beginning.
#

jellyfish.jaro_winkler('Starbucks', 'Starbarbr')

jellyfish.jaro_winkler('Starbucks', 'Milwbucks')

# ##### Soundex
#
# [Soundex](https://en.wikipedia.org/wiki/Soundex) is a phonetic algorithm for indexing names by sound, as pronounced in English. The goal is for homophones to be encoded to the same representation so that they can be matched despite minor differences in spelling. 
#
# Using this algorithm, both "Robert" and "Rupert" return the same string "R163" while "Rubin" yields "R150". "Ashcraft" and "Ashcroft" both yield "A261". "Tymczak" yields "T522" not "T520" (the chars 'z' and 'k' in the name are coded as 2 twice since a vowel lies in between them). "Pfister" yields "P236" not "P123" (the first two letters have the same number and are coded once as 'P').

jellyfish.soundex('Robert')

jellyfish.soundex('Rupert')

jellyfish.soundex('Ashcroft')

jellyfish.soundex('Ashcraft')

jellyfish.soundex('Papadopoylis')

jellyfish.soundex('Papadopoulos')

# ##### Ngrams
#
# With the n-gram similarity score, we split the word into sequences of n consecutive characters (n-grams) and then compare the sets of n-grams between the two words. For example, the name "Panos" has the following 2-grams: "Pa", "an", "no", "os". (We can also add "#P" and "s#" if we want to capture the prefix and suffixes.) Strings that share a large number of q-grams are often similar.

import ngram

ngram.NGram.compare('Ipeirotis','Iperotis',N=2)

ngram.NGram.compare('Ipeirotis','Iperotis',N=1)

ngram.NGram.compare('New York University','New York Universty',N=2)

ngram.NGram.compare('New York University','University of New York',N=1)

ngram.NGram.compare('New York University','Columbia Universty',N=2)

# ### Task 1: Create a function that takes as input two strings and returns their similarity
#
# Given the experience with the metrics above, we want now to create a function that takes as input a string and returns their similarity. Our key requirement is for the similarity metric to be between 0 and 1, with 0 meaning no similarity, and 1 corresponding to identical strings. Some of the similarity functions above would fit right in, others will need some work. 

# +
import ngram
import jellyfish

def normalized_similarity_edit_distance(str1, str2):
    # Compute the similarity between str1 and str2
    distance = ...
    # Normalize
    normalized = ...
    # Return the result
    return ...

    

# + [markdown] solution2="hidden" solution2_first=true
# ### Solution

# + solution2="hidden"
# For n-gram similarity it is very simple, we just return the result
import ngram
def computeSimilarity_ngram(str1, str2, n=3):
    similarity = ngram.NGram.compare(str1,str2,N=n)
    return similarity



# + solution2="hidden"
computeSimilarity_ngram("New York University", "New York Univ")

# + solution2="hidden"
computeSimilarity_ngram("New York University", "New York Univ",n=2)

# + solution2="hidden"
computeSimilarity_ngram("New York University", "New York Univ",n=4)

# + solution2="hidden"
computeSimilarity_ngram("New York University", "Columbia Univ", n=2)

# + solution2="hidden"
# For edit distance
import jellyfish
def computeSimilarity_editdistance(str1, str2):
    # Compute the maximum length of the two strings, to normalize our distance
    maxlength = max( len(str1), len(str2))
    # Compute the edit distance between two strings
    distance = jellyfish.levenshtein_distance(str1, str2)
    similarity = 1 - distance/maxlength
    return similarity

computeSimilarity_editdistance("New York University", "New York Univ")
computeSimilarity_editdistance("New York University", "Columbia Univ")

# + solution2="hidden"
# For soundex
import jellyfish
def computeSimilarity_soundex(str1, str2):
    soundex1 = jellyfish.soundex(str1)
    soundex2 = jellyfish.soundex(str2)
    if soundex1 == soundex2:
        return 1.0
    else: 
        return 0.0
    
computeSimilarity_soundex("New York University", "New York Univ")


# -

# ### Task 2: Modify the functions above to allow for various similarity calculation methods.
#
# We will now up our game, and return back the results of the comparison using various methods. The `method` parameter defines the metric that we will use

def computeSimilarity(str1, str2, method):
    # The function should check the method
    # and then call the appropriate similarity function
    # what we implemented above and return the 
    # corresponding similarity value
    return ...
 


# Getting closer to a real setting, we can now 
# compute all the similarity metrics and return them 
# all. Perhaps even compute an average value
def computeSimilarity(str1, str2):
    # We return a dictionary with all the metrics
    return {
        "ngram2": ...,
        "soundex": ...
    }


# + [markdown] solution2="hidden" solution2_first=true
# ### Solution

# + solution2="hidden"
def computeSimilarity(str1, str2, method):
    if method == 'ngram2':
        return computeSimilarity_ngram(str1, str2,n=2)
    elif method == 'ngram3':
        return computeSimilarity_ngram(str1, str2, n=3)
    elif method == 'ngram4':
        return computeSimilarity_ngram(str1, str2, n=4)
    elif method == 'edit_distance':
        return computeSimilarity_editdistance(str1, str2)
    elif method == 'soundex':
        return computeSimilarity_soundex(str1, str2)
    else:
        return None


# + solution2="hidden"
computeSimilarity("New York University", "New York Univ", 'ngram3')

# + solution2="hidden"
computeSimilarity("New York University", "New York Univ", 'edit_distance')


# + solution2="hidden"
# Most of the time we are going to compute all similarity metrics
# and return back a dictionary with all the metrics
def computeSimilarity(str1, str2):
    results = {
        'ngram2': computeSimilarity_ngram(str1, str2, n=2),
        'ngram3': computeSimilarity_ngram(str1, str2, n=3),
        'ngram4': computeSimilarity_ngram(str1, str2, n=4),
        'edit_distance' : computeSimilarity_editdistance(str1, str2),
        'soundex': computeSimilarity_soundex(str1, str2) 
    }
    # Arbitrarily, compute a similarity metric as the average of all
    results['average'] = sum(results.values()) / len(results)
    # Similarly arbitrarily, we can compute our own metric, by mixing
    # the various metrics in our own way. 
    results['custom'] = (results['ngram3'] + 2.5 * results['edit_distance'] + 0.5 * results['soundex']) / 4
    return results


# + solution2="hidden"
computeSimilarity("New York University", "New York Univ")
# -

# ## STEP 3: Compute similarity of a company against a list of company names

# We now create a function that accepts a company name and a list of companies, and computes their similarity. This part will get us to exercise our for-loops, and also illustrate how we can use lists and tuples.

# **Sorting a list of tuples**:_This part is a little bit advanced for now, so I will just give the code below. (Solution taken from http://stackoverflow.com/questions/3121979/how-to-sort-list-tuple-of-lists-tuples). Here is a small example below, which we will reuse in our function:_

# +
data = [("Panos",0.5), ("Peter",0.8), ("Pan", 0.8)]

# This code sorts the list "data", by using the second element
# of each tuple as the sorting key, and sorts things in reverse order
data.sort(key=lambda tupl: tupl[1], reverse=True)  # sorts in place, in descending order, based on the second element of the tuple
print(data)


# +
# STEP 3: We now create a function that accepts a company name
# and a list of companies, and computes their similarity
# We have a 'top' parameter (by default set to be 5)
# that restricts the results to only the "top" most similar 
# string pairs. We also define a parameter "method" that defines 
# what is the similarity method that we want to use. We also define a 
# similarity threshold for keeping only results with sufficient similarity

def companySimilarity(query, companyList, top = 5, method = 'average', sim_threshold = 0.25):
    ...
    


# + [markdown] solution2="hidden" solution2_first=true
# ### Solution

# + solution2="hidden"
# STEP 3: We now create a function that accepts a company name
# and a list of companies, and computes their similarity
# We have a 'top' parameter (by default set to be 5)
# that restricts the results to only the most similar 
# string pairs. We also define a parameter "method" that defines 
# what is the similarity method that we want to use. We also define a 
# similarity threshold for keeping only results with sufficient similarity

def companySimilarity(query, companyList, top = 5, method = 'average', sim_threshold = 0.25):
    # We will use a list to store the similar matches
    results = []

    # Go through all the restaurants
    for c in companyList:
        # We compute the similarities (all metrics)
        # between the string "query" and the string "c"
        # which is the variable that iterates over the list "companyList"
        similarities = computeSimilarity(query, c)
        # If the ngram similarity is above 0.25
        if similarities[method]>sim_threshold:
            # Add in results the matching restaurant name r
            # and the similarity
            results.append( (c, similarities[method]) )

    # This list contains the matches. The list contains a list
    # of tuples (company name, similarity)
    # We sort in decreasing order of similarity
    results.sort(key=lambda tupl: tupl[1], reverse=True)
    
    # We return only the top results
    return results[:top]    


# + solution2="hidden"
query = 'MACDONALDS'
companySimilarity(query, restaurants, 
                  top = 5, 
                  method = 'ngram3', 
                  sim_threshold = 0.25)


# + solution2="hidden"
query = 'MACDONALDS'
companySimilarity(query, restaurants, 
                  top = 5, 
                  method = 'average', 
                  sim_threshold = 0.25)


# + solution2="hidden"
query = 'STARBUCKS'
companySimilarity(query, restaurants, 
                  top = 5, 
                  method = 'ngram3', 
                  sim_threshold = 0.25)


# + solution2="hidden"
query = 'STARBUCKS'
companySimilarity(query, restaurants, 
                  top = 20, 
                  method = 'average', 
                  sim_threshold = 0.25)

# -

# ## Step 4: Perform the similarity computation across all companies in the dataset.

# We are almost done. We now just go through all the companies in the list
#  and we call the `companySimilarity` function that computes the similar company names
#  _for all the companies in the list_.

# +
# STEP 4: We are almost done. We now just go through all the companies in the list
# and we call the companySimilarity function that computes the similar company names
# for all the companies in the list. We store the results in a dictionary, with the 
# key being the company name, and the value being a "list of tuples" with the 
# similar company names and the corresponding similarity value.

# Your code here

# + [markdown] solution2="hidden" solution2_first=true
# ### Solution

# + solution2="hidden"
# STEP 4: We are almost done. We now just go through all the companies in the list
# and we call the companySimilarity function that computes the similar company names
# for all the companies in the list. We store the results in a dictionary, with the 
# key being the company name, and the value being a "list of tuples" with the 
# similar company names and the corresponding similarity value.


# The matches counter is just to stop the computation quickly
# after we have showed enough matches
matches = 0 
stop_after = 20

for q in restaurants:
    results = companySimilarity(q, restaurants, 
                  top = 6, method = 'average', sim_threshold = 0.4)
    # We will print only non-identical matches (remember the top
    # match is  the restaurant matching with itself)
    if (len(results)>1):
        for r in results[1:]:
            print(f"{q}\t===>\t{r[0]}\t{r[1]:2.3%}")
        matches = matches + 1
    if matches>stop_after: 
        break # We stop after a few illustrative matches 
# -



StarcoderdataJupyterScriptsDedupFiltered