Best practical algorithm for sentence similarity

Cosine Similarity for Vector Space could be you answer.

Or you could calculate the eigenvector of each sentences. But the Problem is, what is similarity?

"This is a tree", "This is not a tree"

If you want to check the semantic meaning of the sentence you will need a wordvector dataset. With the wordvector dataset you will able to check the relationship between words. Example: (King - Man + woman = Queen)

Siraj Raval has a good python notebook for creating wordvector datasets.

One approach you could try is averaging word vectors generated by word embedding algorithms (word2vec, glove, etc). These algorithms create a vector for each word and the cosine similarity among them represents semantic similarity among the words. In the case of the average vectors among the sentences. A good starting point for knowing more about these methods is this paper: How Well Sentence Embeddings Capture Meaning. It discusses some sentence embedding methods. I also suggest you look into Unsupervised Learning of Sentence Embeddings using Compositional n-Gram Features the authors claim their approach beat state of the art methods. Also they provide the code and some usage instructions in this github repo.

bert-as-service offers just that solution.

To answer your question, implementing it yourself from zero would be quite hard as BERT is not a trivial NN, but with this solution you can just plug it in into your algo that uses sentence similarity.

You should check out this. fuzzywuzzy is an awesome library for string/text matching that gives a number between 0 to 100 based on how similar two sentences are. It uses Levenshtein Distance to calculate the differences between sequences in a simple-to-use package. Also, check out this blog post for a detailed explanation of how fuzzywuzzy does the job. This blog is also written by the fuzzywuzzy author

This blog has the solution for short text similarity. They mainly use the BERT neural network model to find similarities between sentences.