What could be a right datascience approach of doing fuzzy string matching in large amount of short text data? I have two lists to compare. List 1 contains strings which represent the strings in List2. Sometimes, they are direct matches, some times, one word match, sometimes there are acronyms etc. An example is as below: 

   List1           |  List2
  ------------------------
   great hall town | Great Hall
   grt_town        | Great Hall      
   gHall           | Great Hall
   great town      | Great Hall
   mind great town | Great Hall


There are two main problems:


List2 is very large ( millions of records, all short in length)
List1 records are very unrelated sometimes. There are longer prefixes, suffixes which are not in List2. Some words in List2 are reduced to a letter. 


I vaguely have some thoughts around clustering List2 and trying to find distance between centroids and the elements from List1. Do you think this as a starting point?
Thanks
You could try this:


Take distinct records from List2
Clean List1 of any extraneous characters or symbols
Use a fuzzy logic package like Python's fuzzywuzzy. It has partial matching options.