notebooks/class_10.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.core.display import HTML\n",
    "import jieba\n",
    "\n",
    "class SearcherIIndex():\n",
    "    \"\"\"倒排索引文本搜索实现类\n",
    "    \n",
    "    用倒排索引\n",
    "    利用Python的集合运算，来实现候选结果集之间交、并运算\n",
    "    \n",
    "    Attributes:\n",
    "        index: 检索使用的倒排索引\n",
    "        max_id: 当前索引的文档最大ID\n",
    "        doc_list: 索引文档原文8\n",
    "    \"\"\"\n",
    "    def __init__(self, docs_file): \n",
    "        \"\"\"初始化，用文件中的文本行构建倒排索引\n",
    "        \n",
    "        Args:\n",
    "            docs_file:包含带索引文档(文本)的文件名\n",
    "            \n",
    "        \"\"\"\n",
    "        self.index = dict()    \n",
    "        self.max_id = 0\n",
    "        self.doc_list = [] \n",
    "        \n",
    "        with open(docs_file, 'r') as f:\n",
    "            docs_data = f.read()\n",
    "        \n",
    "        for doc in docs_data.split():\n",
    "            self.add_doc(doc)\n",
    "\n",
    "    def add_doc(self, doc):\n",
    "        \"\"\"向索引中添加新文档\n",
    "        \n",
    "        Args:\n",
    "            doc:待检索的文档(文本)\n",
    "        \n",
    "        Returns:\n",
    "            新增文档ID\n",
    "        \"\"\"\n",
    "        self.doc_list.append(doc)\n",
    "        for term in list(jieba.cut_for_search(doc)):\n",
    "            #构建和更新各Term对应的Posting(集合)\n",
    "            if term in self.index: \n",
    "                self.index[term].add(self.max_id)\n",
    "            else:\n",
    "                self.index[term] = set([self.max_id])\n",
    "        self.max_id += 1\n",
    "        return self.max_id - 1\n",
    "    \n",
    "    def word_match(self, word):\n",
    "        \"\"\"从倒排索引中获取包含word的候选文档ID集合\n",
    "        \n",
    "        Args:\n",
    "            word:待检索的词(短语)\n",
    "            \n",
    "        Returns：\n",
    "            包含待检索词(短语)的文档ID集合\n",
    "        \"\"\"\n",
    "        result = None\n",
    "        for term in list(jieba.cut(word)):\n",
    "            if result is None:\n",
    "                result = self.index.get(term, set())\n",
    "            else:\n",
    "                result = result & self.index.get(term, set())\n",
    "        if result is None:\n",
    "            result = set()\n",
    "        return result\n",
    "\n",
    "    def conv_query(self, query):\n",
    "        \"\"\"将用户的查询转换成用eval可运行、返回结果ID集合的代码段\n",
    "        \n",
    "        Args:\n",
    "            query:待转换的原始查询字符串\n",
    "        \n",
    "        Returns:\n",
    "            转换完成可通过eval执行返回ID集合的代码段字符串\n",
    "        \"\"\"\n",
    "        query_new_parts = []\n",
    "        all_parts = list(jieba.cut(query))\n",
    "        idx = 0\n",
    "        cache = '' #缓存变量，用于回收分词过程被切开的短语片段\n",
    "        count_parts = len(all_parts)\n",
    "        while idx < count_parts:\n",
    "            if all_parts[idx] == '(' or all_parts[idx] == ')':\n",
    "                query_new_parts.append(all_parts[idx])\n",
    "            elif all_parts[idx] == ' ':\n",
    "                query_new_parts.append(' ')\n",
    "            elif all_parts[idx] in ('and', 'AND', '+'):\n",
    "                query_new_parts.append('&')\n",
    "            elif all_parts[idx] in ('or', 'OR'):\n",
    "                query_new_parts.append('|')\n",
    "            elif all_parts[idx] in ('not', 'NOT', '-'):\n",
    "                query_new_parts.append('-')\n",
    "            elif (idx + 1 < count_parts #被分词切开的短语部分回收至缓存\n",
    "                  and all_parts[idx+1] not in (' ', ')')): \n",
    "                cache += all_parts[idx]\n",
    "            elif (idx + 2 < count_parts #处理词间空格的形式\n",
    "                  and all_parts[idx+1] == \" \" \n",
    "                  and all_parts[idx+2] not in ('(', ')', 'and', 'AND', '+', 'or', 'OR', 'NOT', 'not', '+', '-', ' ')): \n",
    "                query_new_parts.append(\"self.word_match('{}') & \".format(all_parts[idx]))\n",
    "                idx += 2\n",
    "                continue\n",
    "            else:\n",
    "                query_new_parts.append(\"self.word_match('{}')\".format(cache + all_parts[idx]))\n",
    "                cache = '' #合并完成清空缓存\n",
    "            idx += 1\n",
    "        query_new = ''.join(query_new_parts)\n",
    "        return query_new\n",
    "\n",
    "    def highlighter(self, doc, word):\n",
    "        \"\"\"用word对doc进行HTML高亮\n",
    "        \n",
    "        Args:\n",
    "            doc:需要高亮的文档\n",
    "            word:要进行高亮的关键词(查询)\n",
    "            \n",
    "        Returns:\n",
    "            返回对关键词(查询)进行高亮的文档\n",
    "        \"\"\"\n",
    "        for part in list(jieba.cut(word)):\n",
    "            #TODO(CHG):短语高亮需要先分词\n",
    "            if part not in ('(', ')', 'and', 'AND', 'or', 'OR', 'NOT', 'not', ' '):\n",
    "                doc = doc.replace(part, '<span style=\"color:red\">{}</span>'.format(part))\n",
    "        return doc\n",
    "\n",
    "    def search(self, query):\n",
    "        \"\"\"用query进行查询返回结果文档列表\n",
    "        \n",
    "        Args:\n",
    "            query:用户的(复合)布尔查询字符串\n",
    "            \n",
    "        Returns:\n",
    "            复合查询要求的(高亮)文档结果列表\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        query_new = self.conv_query(query)\n",
    "        for did in eval(query_new):\n",
    "            result.append(self.highlighter(self.doc_list[did], query))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "import string\n",
    "\n",
    "class SearcherIIndexVII(SearcherIIndex):\n",
    "    \"\"\"倒排索引文本搜索实现类(改进)\n",
    "    \n",
    "    自定义解析，保留英文片段，将中文片段多粒度分词处理\n",
    "    \n",
    "    Attributes:\n",
    "        index: 检索使用的倒排索引\n",
    "        max_id: 当前索引的文档最大ID\n",
    "        doc_list: 索引文档原文\n",
    "    \"\"\"\n",
    "    def parse_doc(self, doc):\n",
    "        \"\"\"对文档进行自定义解析，保留英文串，对中文串多粒度分词\n",
    "        \n",
    "        Args:\n",
    "            doc:待解析的原始文档\n",
    "        \n",
    "        Returns:\n",
    "            解析结果列表，元素是切分得到的term\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        state_last = ''\n",
    "        cache = ''\n",
    "        for c in doc:\n",
    "            state_c = c in string.ascii_letters \\\n",
    "                or c.isdigit() \\\n",
    "                or c in ('-', ':', '.')\n",
    "            if c == ' ':\n",
    "                if state_last:\n",
    "                    result.append(cache)\n",
    "                else:\n",
    "                    result.extend(list(jieba.cut_for_search(cache)))\n",
    "                result.append(' ')\n",
    "                cache = ''\n",
    "                state_last = '' \n",
    "            else:\n",
    "                if state_c == state_last:\n",
    "                    cache += c\n",
    "                else:\n",
    "                    if state_last != '':\n",
    "                        if state_last:\n",
    "                            result.append(cache)\n",
    "                        else:\n",
    "                            result.extend(list(jieba.cut_for_search(cache)))\n",
    "                    cache = c\n",
    "                state_last = state_c\n",
    "        if cache:\n",
    "            if state_last:\n",
    "                result.append(cache)\n",
    "            else:\n",
    "                result.extend(list(jieba.cut_for_search(cache)))\n",
    "        return result\n",
    "    \n",
    "    def add_doc(self, doc):\n",
    "        \"\"\"向索引中添加新文档(正常索引及ngram索引)\n",
    "        \n",
    "        Args:\n",
    "            doc:待检索的文档(文本)\n",
    "        \n",
    "        Returns:\n",
    "            新增文档ID\n",
    "        \"\"\"\n",
    "        self.doc_list.append(doc)\n",
    "        doc = doc.lower()\n",
    "        for term in self.parse_doc(doc):\n",
    "            #构建和更新各Term对应的Posting(集合)\n",
    "            if term in self.index: \n",
    "                self.index[term].add(self.max_id)\n",
    "            else:\n",
    "                self.index[term] = set([self.max_id])\n",
    "        \n",
    "        #构建ngram索引(以二元为例)\n",
    "        doclen = len(doc)\n",
    "        for i in range(doclen-1):\n",
    "            term = doc[i:i+2]\n",
    "            if term in self.index_b: \n",
    "                self.index_b[term].add(self.max_id)\n",
    "            else:\n",
    "                self.index_b[term] = set([self.max_id])\n",
    "                \n",
    "        self.max_id += 1\n",
    "        return self.max_id - 1\n",
    "    \n",
    "    def dumpIndex(self):\n",
    "        \"\"\"原样输出索引，用于检查索引构建结果\n",
    "        \n",
    "        Returns:\n",
    "            对索引(字典结构)的Dump输出\n",
    "        \"\"\"\n",
    "        print(self.index)\n",
    "    \n",
    "    def conv_query(self, query):\n",
    "        \"\"\"将用户的查询转换成用eval可运行、返回结果ID集合的代码段\n",
    "        \n",
    "        Args:\n",
    "            query:待转换的原始查询字符串\n",
    "        \n",
    "        Returns:\n",
    "            转换完成可通过eval执行返回ID集合的代码段字符串\n",
    "        \"\"\"\n",
    "        query_new_parts = []\n",
    "        all_parts = list(self.parse_query(query))\n",
    "        idx = 0\n",
    "        cache = '' #缓存变量，用于回收分词过程被切开的短语片段\n",
    "        count_parts = len(all_parts)\n",
    "        while idx < count_parts:\n",
    "            if all_parts[idx][1:] == '(' or all_parts[idx][1:] == ')':\n",
    "                query_new_parts.append(all_parts[idx][1:])\n",
    "            elif all_parts[idx][1:] == ' ':\n",
    "                query_new_parts.append(' ')\n",
    "            elif all_parts[idx][1:] in ('and', 'AND', '+'):\n",
    "                query_new_parts.append('&')\n",
    "            elif all_parts[idx][1:] in ('or', 'OR'):\n",
    "                query_new_parts.append('|')\n",
    "            elif all_parts[idx][1:] in ('not', 'NOT', '-'):\n",
    "                query_new_parts.append('-')\n",
    "            elif (idx + 1 < count_parts #对连续的内容分段结果集合中间加”&“运算符\n",
    "                  and all_parts[idx+1][1:] not in (' ', ')')): \n",
    "                query_new_parts.append(\"{} & \".format(self.conv_part(all_parts[idx])))\n",
    "            elif (idx + 2 < count_parts #处理词间、词与符号间空格的情况\n",
    "                  and all_parts[idx+1][1:] == \" \" \n",
    "                  and all_parts[idx+2][1:] not in (')', 'and', 'AND', '+', 'or', 'OR', 'NOT', 'not', '+', '-', ' ')): \n",
    "                query_new_parts.append(\"{} & \".format(self.conv_part(all_parts[idx])))\n",
    "                idx += 2\n",
    "                continue\n",
    "            else:\n",
    "                query_new_parts.append(self.conv_part(cache + all_parts[idx]))\n",
    "                cache = '' #合并完成清空缓存\n",
    "            idx += 1\n",
    "        query_new = ''.join(query_new_parts)\n",
    "        return query_new\n",
    "    \n",
    "    def term_match(self, term):\n",
    "        \"\"\"在索引里找到term对应的posting集合\n",
    "        \n",
    "        Args:\n",
    "            term:要检索的词项\n",
    "            \n",
    "        Results:\n",
    "            term对应的posting集合\n",
    "        \"\"\"\n",
    "        return self.index.get(term, set()) \n",
    "    \n",
    "    def conv_part(self, part):\n",
    "        \"\"\"将带有类别标记的解析结果段 转化为 eval能进行计算的代码段\n",
    "        \n",
    "        Args:\n",
    "            part:带有类别标记的解析结果段\n",
    "            \n",
    "        Results:\n",
    "            eval能进行计算的代码段字符串(调用 term_match() 进行计算)\n",
    "        \"\"\"\n",
    "        flag = part[0]\n",
    "        if flag == 'e':\n",
    "            return \"self.term_match('{}')\".format(part[1:])\n",
    "        elif flag == 'c':\n",
    "            return \"(self.term_match('{}'))\".format(\n",
    "                \"') & self.term_match('\".join(jieba.cut(part[1:])))\n",
    "        elif flag == 'f':\n",
    "            return \"self.frag_match('{}')\".format(part[1:])\n",
    "    \n",
    "    def highlighter(self, doc, query):\n",
    "        \"\"\"用query对doc进行HTML高亮\n",
    "        \n",
    "        Args:\n",
    "            doc:需要高亮的文档\n",
    "            word:要进行高亮的关键词(查询)\n",
    "            \n",
    "        Returns:\n",
    "            返回对关键词(查询)进行高亮的文档\n",
    "        \"\"\"\n",
    "        n = 0\n",
    "        #生成要进行高亮的关键词串集合\n",
    "        word_set = set()\n",
    "        query = query.lower()\n",
    "        query_parts = self.parse_query(query)\n",
    "        for query_part in query_parts:\n",
    "            if query_part[0] == 'e' or query_part[0] == 'f':\n",
    "                word_set.add(query_part[1:])\n",
    "                if len(query_part[1:]) > n:\n",
    "                    n = len(query_part[1:])\n",
    "            elif query_part[0] == 'c':\n",
    "                if len(query_part[1:]) > 1:\n",
    "                    for word in jieba.cut(query_part[1:]):\n",
    "                        word_set.add(word)\n",
    "                        if len(word) > n:\n",
    "                            n = len(word)\n",
    "        \n",
    "        #遍历文档替换高亮关键词串\n",
    "        doc_low = doc.lower()\n",
    "        i = 0\n",
    "        result = []\n",
    "        while True:\n",
    "            end_idx = i + n\n",
    "            if end_idx > len(doc_low):\n",
    "                end_idx = len(doc_low)\n",
    "            for j in range(end_idx, i, -1):\n",
    "                if doc_low[i:j] in word_set:\n",
    "                    break\n",
    "            if doc_low[i:j] in word_set:\n",
    "                result.append(\n",
    "                    '<span style=\"color:red\">{}</span>'.format(doc[i:j]))\n",
    "            else:\n",
    "                result.append(doc_low[i:j])\n",
    "            i = j\n",
    "            if i == len(doc_low):\n",
    "                break\n",
    "                \n",
    "        return ''.join(result)\n",
    "    \n",
    "    def __init__(self, docs_file): \n",
    "        \"\"\"初始化，用文件中的文本行构建倒排索引\n",
    "        \n",
    "        Args:\n",
    "            docs_file:包含带索引文档(文本)的文件名\n",
    "            \n",
    "        \"\"\"\n",
    "        self.index = dict() #标准倒排索引\n",
    "        self.index_b = dict() #ngram索引\n",
    "        self.max_id = 0\n",
    "        self.doc_list = [] \n",
    "        \n",
    "        with open(docs_file, 'r') as f:\n",
    "            docs_data = f.read()\n",
    "        \n",
    "        for doc in docs_data.split():\n",
    "            self.add_doc(doc)\n",
    "            \n",
    "    def frag_match(self, frag):\n",
    "        \"\"\"对片段frag用ngram索引实现原样搜索\n",
    "        \n",
    "        Args:\n",
    "            frag:要原样搜索的字符串\n",
    "            \n",
    "        Results:\n",
    "            片段原样搜索的结果(文档ID)集合\n",
    "        \"\"\"\n",
    "        frag = frag.lower() #大小写归一化\n",
    "        result = None\n",
    "        doclen = len(frag)\n",
    "        for i in range(doclen - 1):\n",
    "            term = frag[i:i+2]\n",
    "            if result is None:\n",
    "                result = self.index_b.get(term, set())\n",
    "            else:\n",
    "                result = result & self.index_b.get(term, set())\n",
    "        return result\n",
    "    \n",
    "    def get_char_type(self, c):\n",
    "        \"\"\"返回当前字符的类型(e,c,s,f,b)\n",
    "        \n",
    "        Args:\n",
    "            c:要进行判断的单个字符\n",
    "            \n",
    "        Results:\n",
    "            返回判断结果(前缀)：e为英文，c为中文，s为空格，f为引号，b为括号\n",
    "        \"\"\"\n",
    "        result = 'c'\n",
    "        if c in string.ascii_letters \\\n",
    "                or c.isdigit() \\\n",
    "                or c in ('-', ':', '.'):\n",
    "            result = 'e'\n",
    "        elif c == '\"':\n",
    "            result = 'f'\n",
    "        elif c == ' ':\n",
    "            result = 's'\n",
    "        elif c in ('(', ')'):\n",
    "            result = 'b'\n",
    "        return result\n",
    "    \n",
    "    def parse_query(self, doc):\n",
    "        \"\"\"对查询进行自定义解析，保留英文串，对中文串原型插入\n",
    "        \n",
    "        Args:\n",
    "            doc:待解析的原始文档\n",
    "        \n",
    "        Returns:\n",
    "            解析结果列表，元素是带有串类型标记(首字符，e为英文，c为中文，s为空格，f为引号，b为括号)\n",
    "            的切分term结果\n",
    "        \"\"\"\n",
    "        doc = doc.lower() + ' ' #解决末位字符状态切换问题的小技巧\n",
    "        result = []\n",
    "        doclen = len(doc)\n",
    "        i = 0\n",
    "        while True:\n",
    "            cur_char_type = self.get_char_type(doc[i])\n",
    "            for j in range(i+1, doclen):\n",
    "                if cur_char_type == 'f': #当前符号为引号，找下一个引号\n",
    "                    if self.get_char_type(doc[j]) == 'f':\n",
    "                        break\n",
    "                elif self.get_char_type(doc[j]) != cur_char_type: #当前符号非引号，找下一个状态变化\n",
    "                    break\n",
    "            if cur_char_type == 's': #对多个空格连续出现的情况进行合并\n",
    "                result.append('s ')\n",
    "            elif cur_char_type == 'f': #对引号只提取引号内字符串\n",
    "                result.append(cur_char_type + doc[i+1:j])\n",
    "                j += 1\n",
    "            else:\n",
    "                result.append(cur_char_type + doc[i:j])\n",
    "            i = j\n",
    "            if i >= doclen - 1:\n",
    "                break\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['f七连胜']\n",
      "['一边倒！中国女排3-0横扫美国取<span style=\"color:red\">七连胜</span>', '一边倒！中国女排3-0横扫美国取<span style=\"color:red\">七连胜</span>', '一边倒！中国女排3-0横扫美国取<span style=\"color:red\">七连胜</span>', '一边倒！中国女排3-0横扫美国取<span style=\"color:red\">七连胜</span>', '一边倒！中国女排3-0横扫美国取<span style=\"color:red\">七连胜</span>']\n"
     ]
    }
   ],
   "source": [
    "query = '\"七连胜\"'\n",
    "searcher = SearcherIIndexVII('titles.txt')\n",
    "print(searcher.parse_query(query))\n",
    "print(searcher.search(query))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['fmate']\n",
      "self.frag_match('mate')\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "外媒评<span style=\"color:red\">Mate</span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"color:red\">Mate</span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "怼完苹果怼三星，刚发了<span style=\"color:red\">Mate</span>30的余承东依然要"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "华为<span style=\"color:red\">Mate</span>30采用安卓系统"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "可安装谷歌gms！华为<span style=\"color:red\">Mate</span>30确认支持boo"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"color:red\">Mate</span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "余承东:<span style=\"color:red\">Mate</span>30"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "iphone11和华为<span style=\"color:red\">Mate</span>30拍照对比：差距"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"color:red\">Mate</span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "外媒评<span style=\"color:red\">Mate</span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "怼完苹果怼三星，刚发了<span style=\"color:red\">Mate</span>30的余承东依然要"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "外媒评华为<span style=\"color:red\">Mate</span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "余承东:<span style=\"color:red\">Mate</span>30"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "华为<span style=\"color:red\">Mate</span>30采用安卓系统"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "华为发布<span style=\"color:red\">Mate</span>30系列手机：电池最大4500m"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "怼完苹果怼三星，刚发了<span style=\"color:red\">Mate</span>30的余承东依然要"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "searcher = SearcherIIndexVII('titles.txt')\n",
    "\n",
    "query = '\"mate\"'\n",
    "print(searcher.parse_query(query))\n",
    "print(searcher.conv_query(query))\n",
    "result = searcher.search(query)\n",
    "if result:\n",
    "    for doc in result:\n",
    "        display(HTML(doc))\n",
    "else:\n",
    "    print('No result.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['A', 'a', 'aa', 'aal', 'aalii', 'aam', 'Aani', 'aardvark', 'aardwolf', 'Aaron']\n"
     ]
    }
   ],
   "source": [
    "import nltk\n",
    "print(nltk.corpus.words.words()[:10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "import nltk\n",
    "\n",
    "class Corrector():\n",
    "    \"\"\"用二元索引实现拼写校正\n",
    "    \n",
    "    Attributes:\n",
    "        index_b: 检索使用的二元索引\n",
    "        max_id: 当前索引的单词最大ID\n",
    "        doc_list: 索引单词原文\n",
    "    \"\"\"\n",
    "    def __init__(self): \n",
    "        \"\"\"初始化，用NLTK的words词典构建倒排索引\n",
    "        \"\"\"\n",
    "        self.index_b = dict() #ngram索引\n",
    "        self.max_id = 0\n",
    "        self.doc_list = [] \n",
    "        \n",
    "        for doc in nltk.corpus.words.words():\n",
    "            self.add_doc(doc)\n",
    "            \n",
    "    def add_doc(self, doc):\n",
    "        \"\"\"向索引中添加新词(单词的二元索引)\n",
    "        \n",
    "        Args:\n",
    "            doc:待检索的单词\n",
    "        \n",
    "        Returns:\n",
    "            新增单词ID\n",
    "        \"\"\"\n",
    "        self.doc_list.append(doc)\n",
    "        doc = doc.lower()\n",
    "        \n",
    "        #构建二元索引\n",
    "        doclen = len(doc)\n",
    "        for i in range(doclen-1):\n",
    "            term = doc[i:i+2]\n",
    "            if term in self.index_b: \n",
    "                self.index_b[term].append(self.max_id)\n",
    "            else:\n",
    "                self.index_b[term] = [self.max_id]\n",
    "                \n",
    "        self.max_id += 1\n",
    "        return self.max_id - 1\n",
    "    \n",
    "    def correct(self, word, limit=5):\n",
    "        \"\"\"拼写校正函数\n",
    "        \n",
    "        Args:\n",
    "            word:待校正的词\n",
    "            limit:返回结果的最大条数，默认值为5\n",
    "            \n",
    "        Returns:\n",
    "            最可能的校正单词列表\n",
    "        \"\"\"\n",
    "        word = word.lower() #大小写归一化\n",
    "        result = []\n",
    "        docid_list = []\n",
    "        doclen = len(word)\n",
    "        for i in range(doclen - 1):\n",
    "            term = word[i:i+2]\n",
    "            docid_list += self.index_b.get(term, [])\n",
    "        docid_counter = Counter(docid_list)\n",
    "        count = 0\n",
    "        for elem in docid_counter.most_common(300):\n",
    "            cor_word = self.doc_list[elem[0]]\n",
    "            if len(cor_word) >= doclen - 1 and len(cor_word) <= doclen + 1:\n",
    "                result.append(cor_word)\n",
    "                count += 1\n",
    "                if count > limit:\n",
    "                    break\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "cor = Corrector()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['retrieval', 'pretribal', 'rearrival', 'rerival', 'retreatal', 'retrial']\n"
     ]
    }
   ],
   "source": [
    "print(cor.correct('retrival'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({1: 2, 2: 1, 3: 1, 4: 1})"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import Counter\n",
    "\n",
    "Counter([1,1,2,3,4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> \u001b[0;32m<ipython-input-13-c918f0d68a99>\u001b[0m(168)\u001b[0;36mconv_query\u001b[0;34m()\u001b[0m\n",
      "\u001b[0;32m    166 \u001b[0;31m                \u001b[0mcache\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m''\u001b[0m \u001b[0;31m#合并完成清空缓存\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[0;32m    167 \u001b[0;31m            \u001b[0midx\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[0;32m--> 168 \u001b[0;31m        \u001b[0mquery_new\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m''\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mjoin\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mquery_new_parts\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[0;32m    169 \u001b[0;31m        \u001b[0;32mreturn\u001b[0m \u001b[0mquery_new\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[0;32m    170 \u001b[0;31m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0m\n"
     ]
    },
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "ipdb>  quit\n"
     ]
    }
   ],
   "source": [
    "%debug"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "华为|M|a|t|e|3|0|采|用|安卓系统\n",
      "华为|M|a|t|e|3|0|采|用|安卓系统\n"
     ]
    }
   ],
   "source": [
    "doc = '华为Mate30采用安卓系统'\n",
    "\n",
    "n = 6\n",
    "word_set = set(\n",
    "    ['华为' ,'安卓', '安卓系统'])\n",
    "\n",
    "#正向最大分词\n",
    "i = 0\n",
    "result_f = []\n",
    "while True:\n",
    "    end_idx = i + n\n",
    "    if end_idx > len(doc):\n",
    "        end_idx = len(doc)\n",
    "    for j in range(end_idx, i, -1):\n",
    "        if doc[i:j] in word_set:\n",
    "            break\n",
    "    result_f.append(doc[i:j])\n",
    "    i = j\n",
    "    if i == len(doc):\n",
    "        break\n",
    "print('|'.join(result_f))\n",
    "\n",
    "#逆向最大分词\n",
    "i = len(doc)\n",
    "result_b = []\n",
    "while True:\n",
    "    end_idx = i - n\n",
    "    if end_idx < 0:\n",
    "        end_idx = 0\n",
    "    for j in range(end_idx, i):\n",
    "#         print(j,i,doc[j:i])\n",
    "        if doc[j:i] in word_set:\n",
    "            break\n",
    "    result_b.insert(0, doc[j:i])\n",
    "    i = j\n",
    "    if i == 0:\n",
    "        break\n",
    "print('|'.join(result_b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 4, 3, 2, 1]"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#列表倒序的简单方法：切片法\n",
    "[1, 2, 3, 4, 5][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}