How to group sentences by edit distance?
There is only a limited set of POS tags.
Rather than using edit distance, compute a POS-POS similarity matrix just once. You may even want to edit this matrixes desired, e.g. to make two POS tags effectively the same, or to increase the difference of two tags.
Store that in a numpy array, convert all your vectors to indexes, and then compute similarities using that lookup table. For performance reasons, use numpy where possible, and write the performance critical code in cython because the Python interpreter is very slow.
I have a large set (36k sentence) of sentences (text list) and their POS tags (POS list), and I'd like to group/cluster the elements in the POS list using edit distance/Levenshtein:
(e.g Sentx POS tags= [CC DT VBZ RB JJ], Senty POS tags= [CC DT VBZ RB JJ] ) are in cluster edit distance =0, 
while ([CC DT VBZ RB JJ], [CC DT VB RB JJ]) are in cluster edit distance =1. 
I understand how the clustering algorithms work but I am confused how to approach such a problem in python and how to store the clusters in data structures so that I can retrieve them easily.
I tried to create a matrix (measuring the distance of each sentence with all the sentences in the corpus) but it takes very long to be processed.