Python68-计算两个字符串相(或句子)似度的方法.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "主要方法有：编辑距离、余弦相似度、模糊相似度百分比"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1 编辑距离\n",
    "- [编辑距离（Levenshtein距离）详解（附python实现）](https://blog.csdn.net/luo123n/article/details/9999481)\n",
    "- [使用Python计算文本相似性之编辑距离](https://www.biaodianfu.com/edit-distance.html)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def levenshtein(first, second):\n",
    "        ''' 编辑距离算法（LevD） \n",
    "            Args: 两个字符串\n",
    "            returns: 两个字符串的编辑距离 int\n",
    "        '''\n",
    "        if len(first) > len(second):\n",
    "            first, second = second, first\n",
    "        if len(first) == 0:\n",
    "            return len(second)\n",
    "        if len(second) == 0:\n",
    "            return len(first)\n",
    "        first_length = len(first) + 1\n",
    "        second_length = len(second) + 1\n",
    "        distance_matrix = [list(range(second_length)) for x in range(first_length)]\n",
    "        # print distance_matrix\n",
    "        for i in range(1, first_length):\n",
    "            for j in range(1, second_length):\n",
    "                deletion = distance_matrix[i - 1][j] + 1\n",
    "                insertion = distance_matrix[i][j - 1] + 1\n",
    "                substitution = distance_matrix[i - 1][j - 1]\n",
    "                if first[i - 1] != second[j - 1]:\n",
    "                    substitution += 1\n",
    "                distance_matrix[i][j] = min(insertion, deletion, substitution)\n",
    "                # print distance_matrix\n",
    "        return distance_matrix[first_length - 1][second_length - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "str1=\"hello,good moring\"\n",
    "str2=\"hi,good moring\"\n",
    "edit_distance=levenshtein(str1,str2)\n",
    "edit_distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python中的Levenshtein包可以方便的计算编辑距离，包的安装： pip install python-Levenshtein"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import Levenshtein\n",
    "text_a='编辑距离'\n",
    "text_b='编辑距离，走起'\n",
    "Levenshtein.distance(text_a,text_b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2 余弦相似度\n",
    "- [余弦计算相似度度量](https://blog.csdn.net/u012160689/article/details/15341303)\n",
    "- [python用余弦相似度计算英文文本相似度](https://blog.csdn.net/u012160689/article/details/15341303)\n",
    "- [https://blog.csdn.net/u013749540/article/details/51813922](https://blog.csdn.net/u013749540/article/details/51813922)图片很美"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'this': 1, 'game': 2, 'is': 1, 'one': 1, 'of': 1, 'the': 4, 'very': 1, 'best': 1, 'games': 1, 'ive': 1, 'played': 1, 'pictures': 1, 'cant': 1, 'descripe': 1, 'real': 1, 'graphics': 1, 'in': 1}\n",
      "{'this': 1, 'game': 2, 'have': 1, 'is': 1, 'one': 1, 'of': 1, 'the': 4, 'very': 1, 'best': 1, 'games': 1, 'ive': 1, 'played': 1, 'pictures': 1, 'cant': 1, 'descripe': 1, 'now': 1, 'real': 1, 'graphics': 1, 'in': 1}\n",
      "[('the', 4), ('game', 2), ('this', 1), ('is', 1), ('one', 1), ('of', 1), ('very', 1), ('best', 1), ('games', 1), ('ive', 1), ('played', 1), ('pictures', 1), ('cant', 1), ('descripe', 1), ('real', 1), ('graphics', 1), ('in', 1)]\n",
      "[('the', 4), ('game', 2), ('this', 1), ('have', 1), ('is', 1), ('one', 1), ('of', 1), ('very', 1), ('best', 1), ('games', 1), ('ive', 1), ('played', 1), ('pictures', 1), ('cant', 1), ('descripe', 1), ('now', 1), ('real', 1), ('graphics', 1), ('in', 1)]\n",
      "[4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0]\n",
      "[4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "0.97\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "import re\n",
    "import datetime\n",
    "import time\n",
    "\n",
    "text1 = \"This game is one of the very best. games ive  played. the  ;pictures? \" \\\n",
    "        \"cant descripe the real graphics in the game.\"\n",
    "text2 = \"this game have/ is3 one of the very best. games ive  played. the  ;pictures? \" \\\n",
    "        \"cant descriPe now the real graphics in the game.\"\n",
    "text3 = \"So in the picture i saw a nice size detailed metal puzzle. Eager to try since I enjoy 3d wood puzzles, i ordered it. Well to my disappointment I got in the mail a small square about 4 inches around. And to add more disappointment when I built it it was smaller than the palm of my hand. For the price it should of been much much larger. Don't be fooled. It's only worth $5.00.Update 4/15/2013I have bought and completed 13 of these MODELS from A.C. Moore for $5.99 a piece, so i stand by my comment that thiss one is overpriced. It was still fun to build just like all the others from the maker of this brand.Just be warned, They are small.\"\n",
    "text4 = \"I love it when an author can bring you into their made up world and make you feel like a friend, confidant, or family. Having a special child of my own I could relate to the teacher and her madcap class. I've also spent time in similar classrooms and enjoyed the uniqueness of each and every child. Her story drew me into their world and had me laughing so hard my family thought I had lost my mind, so I shared the passage so they could laugh with me. Read this book if you enjoy a book with strong women, you won't regret it.\"\n",
    "\n",
    "def compute_cosine(text_a, text_b):\n",
    "    # 找单词及词频\n",
    "    words1 = text_a.split(' ')\n",
    "    words2 = text_b.split(' ')\n",
    "    # print(words1)\n",
    "    words1_dict = {}\n",
    "    words2_dict = {}\n",
    "    for word in words1:\n",
    "        # word = word.strip(\",.?!;\")\n",
    "        word = re.sub('[^a-zA-Z]', '', word)\n",
    "        word = word.lower()\n",
    "        # print(word)\n",
    "        if word != '' and word in words1_dict: # 这里改动了\n",
    "            num = words1_dict[word]\n",
    "            words1_dict[word] = num + 1\n",
    "        elif word != '':\n",
    "            words1_dict[word] = 1\n",
    "        else:\n",
    "            continue\n",
    "    for word in words2:\n",
    "        # word = word.strip(\",.?!;\")\n",
    "        word = re.sub('[^a-zA-Z]', '', word)\n",
    "        word = word.lower()\n",
    "        if word != '' and word in words2_dict:\n",
    "            num = words2_dict[word]\n",
    "            words2_dict[word] = num + 1\n",
    "        elif word != '':\n",
    "            words2_dict[word] = 1\n",
    "        else:\n",
    "            continue\n",
    "    print(words1_dict)\n",
    "    print(words2_dict)\n",
    "    \n",
    "    # 排序\n",
    "    dic1 = sorted(words1_dict.items(), key=lambda asd: asd[1], reverse=True)\n",
    "    dic2 = sorted(words2_dict.items(), key=lambda asd: asd[1], reverse=True)\n",
    "    print(dic1)\n",
    "    print(dic2)\n",
    "\n",
    "    # 得到词向量\n",
    "    words_key = []\n",
    "    for i in range(len(dic1)):\n",
    "        words_key.append(dic1[i][0])  # 向数组中添加元素\n",
    "    for i in range(len(dic2)):\n",
    "        if dic2[i][0] in words_key:\n",
    "            # print 'has_key', dic2[i][0]\n",
    "            pass\n",
    "        else:  # 合并\n",
    "            words_key.append(dic2[i][0])\n",
    "    # print(words_key)\n",
    "    vect1 = []\n",
    "    vect2 = []\n",
    "    for word in words_key:\n",
    "        if word in words1_dict:\n",
    "            vect1.append(words1_dict[word])\n",
    "        else:\n",
    "            vect1.append(0)\n",
    "        if word in words2_dict:\n",
    "            vect2.append(words2_dict[word])\n",
    "        else:\n",
    "            vect2.append(0)\n",
    "    print(vect1)\n",
    "    print(vect2)\n",
    "\n",
    "    # 计算余弦相似度\n",
    "    sum = 0\n",
    "    sq1 = 0\n",
    "    sq2 = 0\n",
    "    for i in range(len(vect1)):\n",
    "        sum += vect1[i] * vect2[i]\n",
    "        sq1 += pow(vect1[i], 2)\n",
    "        sq2 += pow(vect2[i], 2)\n",
    "    try:\n",
    "        result = round(float(sum) / (math.sqrt(sq1) * math.sqrt(sq2)), 2)\n",
    "    except ZeroDivisionError:\n",
    "        result = 0.0\n",
    "    # print(result)\n",
    "    return result\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    result=compute_cosine(text1, text2)\n",
    "    print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3 FuzzyWuzzy\n",
    "- [fuzzywuzzy](https://github.com/seatgeek/fuzzywuzzy)\n",
    "- [FuzzyWuzzy: Fuzzy String Matching in Python](http://chairnerd.seatgeek.com/fuzzywuzzy-fuzzy-string-matching-in-python/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "E:\\ProgramData\\Anaconda3\\lib\\site-packages\\fuzzywuzzy\\fuzz.py:35: UserWarning: Using slow pure-python SequenceMatcher. Install python-Levenshtein to remove this warning\n",
      "  warnings.warn('Using slow pure-python SequenceMatcher. Install python-Levenshtein to remove this warning')\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "97"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from fuzzywuzzy import fuzz\n",
    "fuzz.ratio(\"this is a test\", \"this is a test!\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}