{"cells":[{"metadata":{},"cell_type":"markdown","source":"# BMS molecular translation"},{"metadata":{},"cell_type":"markdown","source":"In this notebook I will implement the [Levenshtein distance](https://en.wikipedia.org/wiki/Levenshtein_distance) metric with examples. If you find this helpful please upvote."},{"metadata":{"trusted":true},"cell_type":"code","source":"import numpy as np","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true},"cell_type":"code","source":"def levenshtein_distance(a, b)-> str:\n    \n    d = np.zeros((len(a), len(b)))\n    \n    for i in range(len(a)):\n        d[i, 0] = i\n    \n    for j in range(len(b)):\n        d[0, j] = j\n    \n    for j in range(len(b)):\n        for i in range(len(a)):\n            if a[i] == b[j]:\n                cost = 0\n            else:\n                cost = 1\n            d[i, j] = min(d[i-1, j]+1, d[i, j-1] + 1,d[i-1, j-1] + cost)\n    return d[len(a)-1, len(b)-1]","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"levenshtein_distance('kitten', 'sitting') # k, i and g","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"levenshtein_distance('InChI=1S/C13H20OS/c1-9(2)8-15-13-6-5-10(3)7-12(13)11(4)14/h5-7,9,11,14H,8H2,1-4H3',\n                    'InChI=C13H20OS/c1-9(2)8-15-13-6-5-10(3)7-12(13)11(4)14/h5-7,9,11,14H,8H2,1-4H3')\n# Removed 1S/ in the second sequence","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"levenshtein_distance('hello', 'yellow')   # y and w are different","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat":4,"nbformat_minor":4}