String Similarity using fuzzywuzzy on big data
The first algorithmic recommendation is to use itertools.combinations instead of .permutations, since you don't care about order. This assumes fuzz.token_sort_ratio(str_1, str_2) == fuzz.token_sort_ratio(str_2, str_1). There are half as many combinations as there are permutations, so that gives you a free 2x speedup.

This code also lends itself easily to parallelization. On an i7 (8 virtual cores, 4 physical), you could probably expect this to give you ~4-8x speedup, but that depends on a lot of factors. The least intrusive way to do this is to use multiprocessing.Pool.map or .imap_unordered:

import multiprocessing as mp

def ratio(strings):
    s1, s2 = strings
    return s1, s2, fuzz.token_sort_ratio(s1, s2)

with open('D:\\Sim_Score.csv', 'w') as f1:
    writer = csv.writer(f1, delimiter='\t', lineterminator='\n', )
    writer.writerow(['tag4'])

    with mp.Pool() as pool:
        for s1, s2, r in pool.imap_unordered(ratio, itertools.combinations(Dishes, 2)):
            if r &gt; threshold_ratio:
                writer.writerow([(s1, s2, r)])


All told, I'd expect these changes to give you 5-10x speedup, depending heavily on the number of cores you have available.

For reference, a generator comprehension version of this might look something like:

with mp.Pool() as pool:
    writer.writerows((s1, s2, r)
                     for s1, s2, r in pool.imap_unordered(ratio, itertools.combinations(Dishes, 2))
                     if r &gt; threshold_ratio)


That version has a some, but very little, performance improvement over the non-comprehension version, and IMO is harder to read/maintain.

One other minor thing I noticed in testing my code was that fuzzywuzzy recommends installing python-Levenshtein in order to run faster; when I did so, it ran about 20x slower than when it used the built-in SequenceMatcher. When I uninstalled python-Levenshtein it got fast again. That seems very odd to me, but it's certainly something worth trying.

Finally, if performance is important, you could consider digging into what fuzz.token_sort_ratio does to see if you could remove some repeated work. For example, it's tokenizing and sorting each string again every time you pass it in, so maybe you could pre-tokenize/sort the strings and only run the ratio logic inside the main loop. A quick dig tells me that token_sort_ratio is two main steps:


Preprocess each string using fuzz._process_and_sort
Run fuzz.partial_ratio against the processed strings


I'm not able to get this to run faster at the moment, but I'll edit and update this answer if I can get that approach to work well.