<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 String Matching
The idea of string matching is to find strings that match a given pattern. We have seen that Pandas provides some useful functions to do that job.
Step1:  Imagine I want to have a list of my friends with the amount of money I borrowed to each other, toghether with their names and surnames.
Step2:  To merge two dataframes we can use merge function
Step3:  Approximate String Matching
Fuzzy String Matching, also called Approximate String Matching, is the process of finding strings that approximatively match a given pattern.
For example, we can have two datasets with information about local municipalities
Step4:  The closeness of a match is often measured in terms of edit distance, which is the number of primitive operations necessary to convert the string into an exact match.
Primitive operations are usually
Step5:  Partial String Similarity
What to do when we want to find if two strings are simmilar, and one contains the other.
In this case the ratio will be low but if we would know how to split the bigger string, the match would be perfect. Let's see an example
Step6:  In fact we can have the following situation
Step7:  partial_ratio, seeks the more appealing substring and returns its ratio
Step8:  Out of Order
What happens if we have just the same strings but in a different order, let's have an example
Step9:  FuzzyWuzzy provides two ways to deal with this situation
Step10:  Token Set
The token set approach is similar, but a little bit more flexible. Here, we tokenize both strings, but instead of immediately sorting and comparing, we split the tokens into two groups
Step11:  Example
We want to merge both mun_codes and lat_lon_mun. So we have to have a good municipality name in both datasets. From that names we can do
Step12:  Step 2
Step13:  Step 3
Step14:  Step 4
Step15:  Step 5
Step16:  Step 6
<ASSISTANT_TASK:>
Python Code:
import pandas as pd
names = pd.DataFrame({"name" : ["Alice","Bob","Charlie","Dennis"],
                     "surname" : ["Doe","Smith","Sheen","Quaid"]})
names
names.name.str.match("A\w+")
debts = pd.DataFrame({"debtor":["D.Quaid","C.Sheen"],
                     "amount":[100,10000]})
debts
Explanation: String Matching
The idea of string matching is to find strings that match a given pattern. We have seen that Pandas provides some useful functions to do that job.
End of explanation
debts["surname"] = debts.debtor.str.extract("\w+\.(\w+)")
debts
Explanation: Imagine I want to have a list of my friends with the amount of money I borrowed to each other, toghether with their names and surnames.
End of explanation
names.merge(debts, left_on="surname", right_on="surname", how="left")
names.merge(debts, left_on="surname", right_on="surname", how="right")
names.merge(debts, left_on="surname", right_on="surname", how="inner")
names.merge(debts, left_on="surname", right_on="surname", how="outer")
names.merge(debts, left_index=True, right_index=True, how="left")
Explanation: To merge two dataframes we can use merge function: https://pandas.pydata.org/pandas-docs/stable/generated/pandas.DataFrame.merge.html. Merge DataFrame objects by performing a database-style join operation by columns or indexes.
We can use merge in two different ways (very simmilar):
* using the DataFrame method: left_df.merge(right_df, ...)
* using the Pandas function: pd.merge(left_df, right_df, ...)
Common parameters   
how : {‘left’, ‘right’, ‘outer’, ‘inner’}, default ‘inner’
left: use only keys from left frame, similar to a SQL left outer join; preserve key order
right: use only keys from right frame, similar to a SQL right outer join; preserve key order
outer: use union of keys from both frames, similar to a SQL full outer join; sort keys lexicographically
inner: use intersection of keys from both frames, similar to a SQL inner join; preserve the order of the left keys
on : label or list
Field names to join on. Must be found in both DataFrames. If on is None and not merging on indexes, then it merges on the intersection of the columns by default.
left_on : label or list, or array-like
Field names to join on in left DataFrame. Can be a vector or list of vectors of the length of the DataFrame to use a particular vector as the join key instead of columns
right_on : label or list, or array-like
Field names to join on in right DataFrame or vector/list of vectors per left_on docs
left_index : boolean, default False
Use the index from the left DataFrame as the join key(s). If it is a MultiIndex, the number of keys in the other DataFrame (either the index or a number of columns) must match the number of levels
right_index : boolean, default False
Use the index from the right DataFrame as the join key. Same caveats as left_index
End of explanation
lat_lon_mun = pd.read_excel("lat_lon_municipalities.xls", skiprows=2)
lat_lon_mun.head()
mun_codes = pd.read_excel("11codmun.xls", encoding="latin1", skiprows=1) 
mun_codes.head()
lat_lon_mun[lat_lon_mun["Población"].str.match(".*anaria.*")]
mun_codes[mun_codes["NOMBRE"].str.match(".*anaria.*")]
"Valsequillo de Gran Canaria" == "Valsequillo de Gran Canaria"
"Palmas de Gran Canaria (Las)" == "Palmas de Gran Canaria, Las"
Explanation: Approximate String Matching
Fuzzy String Matching, also called Approximate String Matching, is the process of finding strings that approximatively match a given pattern.
For example, we can have two datasets with information about local municipalities:
End of explanation
from fuzzywuzzy import fuzz
fuzz.ratio("NEW YORK METS","NEW YORK MEATS")
fuzz.ratio("Palmas de Gran Canaria (Las)","Palmas de Gran Canaria, Las")
Explanation: The closeness of a match is often measured in terms of edit distance, which is the number of primitive operations necessary to convert the string into an exact match.
Primitive operations are usually: insertion (to insert a new character at a given position), deletion (to delete a particular character) and substitution (to replace a character with a new one).
Fuzzy String Matching can have different practical applications. Typical examples are spell-checking, text re-use detection (the politically correct way of calling plagiarism detection), spam filtering, as well as several applications in the bioinformatics domain, e.g. matching DNA sequences.
FuzzyWuzzy
The main modules in FuzzyWuzzy are called fuzz, for string-to-string comparisons, and process to compare a string with a list of strings.
Under the hood, FuzzyWuzzy uses difflib, part of the standard library, so there is nothing extra to install. 
String Similarity
The simplest way to compare two strings is with a measurement of edit distance. For example, the following two strings are quite similar:
NEW YORK METS
NEW YORK MEATS
Now, according to the ratio:
Return a measure of the sequences' similarity as a float in the range [0, 1]. Where T is the total number of elements in both sequences, and M is the number of matches, this is 2.0*M / T.
End of explanation
"San Millán de Yécora" == "Millán de Yécora"
fuzz.ratio("San Millán de Yécora", "Millán de Yécora")
Explanation: Partial String Similarity
What to do when we want to find if two strings are simmilar, and one contains the other.
In this case the ratio will be low but if we would know how to split the bigger string, the match would be perfect. Let's see an example:
End of explanation
fuzz.ratio("YANKEES", "NEW YORK YANKEES") 
fuzz.ratio("NEW YORK METS", "NEW YORK YANKEES")
Explanation: In fact we can have the following situation:
End of explanation
fuzz.partial_ratio("San Millán de Yécora", "Millán de Yécora")
fuzz.partial_ratio("YANKEES", "NEW YORK YANKEES") 
fuzz.partial_ratio("NEW YORK METS", "NEW YORK YANKEES") 
Explanation: partial_ratio, seeks the more appealing substring and returns its ratio
End of explanation
s1 = "Las Palmas de Gran Canaria"
s2 = "Gran Canaria, Las Palmas de"
s3 = "Palmas de Gran Canaria, Las"
s4 = "Palmas de Gran Canaria, (Las)"
Explanation: Out of Order
What happens if we have just the same strings but in a different order, let's have an example:
End of explanation
fuzz.token_sort_ratio("Las Palmas de Gran Canaria", "Palmas de Gran Canaria Las")
fuzz.ratio("Las Palmas de Gran Canaria", "Palmas de Gran Canaria Las")
Explanation: FuzzyWuzzy provides two ways to deal with this situation:
Token Sort
The token sort approach involves tokenizing the string in question, sorting the tokens alphabetically, and then joining them back into a string. Then compare the transformed strings with a simple ratio(.
End of explanation
t0 = ["Canaria,","de","Gran", "Palmas"]
t1 = ["Canaria,","de","Gran", "Palmas"] + ["Las"]
t2 = ["Canaria,","de","Gran", "Palmas"] + ["(Las)"]
fuzz.token_sort_ratio("Palmas de Gran Canaria, Las", "Palmas de Gran Canaria, (Las)")
Explanation: Token Set
The token set approach is similar, but a little bit more flexible. Here, we tokenize both strings, but instead of immediately sorting and comparing, we split the tokens into two groups: intersection and remainder. We use those sets to build up a comparison string.
t0 = [SORTED_INTERSECTION]
t1 = [SORTED_INTERSECTION] + [SORTED_REST_OF_STRING1]
t2 = [SORTED_INTERSECTION] + [SORTED_REST_OF_STRING2]
max(ratio(t0,t1),ratio(t0,t2),ratio(t1,t2))
End of explanation
mun_codes.shape
mun_codes.head()
lat_lon_mun.shape
lat_lon_mun.head()
Explanation: Example
We want to merge both mun_codes and lat_lon_mun. So we have to have a good municipality name in both datasets. From that names we can do:
 * Exact string matching: match these names common in both datasets
 * Approximate string matching: match these names with highest similarity
Step 1: Explore datasets
End of explanation
df1 = mun_codes.merge(lat_lon_mun, left_on="NOMBRE", right_on="Población",how="inner")
df1.head()
Explanation: Step 2: Merge datasets
End of explanation
df1["match_ratio"] = 100
Explanation: Step 3: Create a new variable called match_ratio
End of explanation
df2 = mun_codes.merge(df1, left_on="NOMBRE", right_on="NOMBRE", how="left")
df2.head()
df3 = df2.loc[: ,["CPRO_x","CMUN_x","DC_x","NOMBRE","match_ratio"]]
df3.rename(columns={"CPRO_x": "CPRO", "CMUN_x":"CMUN","DC_x":"DC"},inplace=True)
df3.head()
df3.loc[df3.match_ratio.isnull(),:].head()
Explanation: Step 4: Merge again with original dataset and select those which have no direct match
End of explanation
mun_names = lat_lon_mun["Población"].tolist()
def approx_str_compare(x):
    ratio = [fuzz.ratio(x,m) for m in mun_names]
    res = pd.DataFrame({"ratio" : ratio,
                "name": mun_names})
    return res.sort_values(by="ratio",ascending=False).iloc[0,:]
    
df4 = df3.loc[df3.match_ratio.isnull(),"NOMBRE"].map(approx_str_compare)
Explanation: Step 5: Apply approximate string matching
End of explanation
df4.map(lambda x: x["name"])
df4.map(lambda x: x["ratio"])
df6 = df3.loc[df3.match_ratio.isnull(),:]
df6["match_ratio"] = df4.map(lambda x: x["ratio"])
df6["NOMBRE"] = df4.map(lambda x: x["name"])
df6.head()
df7 = pd.concat([df3,df6])
Explanation: Step 6: Concatenate results
End of explanation
<END_TASK>