notebooks/class_8.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "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": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Building prefix dict from the default dictionary ...\n",
      "Loading model from cache /var/folders/8t/p4w9tmzx5413xgf7hpr2sj7r0000gn/T/jieba.cache\n",
      "Loading model cost 0.866 seconds.\n",
      "Prefix dict has been built succesfully.\n"
     ]
    },
    {
     "ename": "TypeError",
     "evalue": "bad operand type for unary -: 'set'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-3-3ee04a7a510b>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0mquery\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m'3-0'\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msearcher\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msearch\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mquery\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      5\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0mdoc\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-2-bb2bbaf54146>\u001b[0m in \u001b[0;36msearch\u001b[0;34m(self, query)\u001b[0m\n\u001b[1;32m    136\u001b[0m         \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    137\u001b[0m         \u001b[0mquery_new\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconv_query\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mquery\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 138\u001b[0;31m         \u001b[0;32mfor\u001b[0m \u001b[0mdid\u001b[0m \u001b[0;32min\u001b[0m \u001b[0meval\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mquery_new\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    139\u001b[0m             \u001b[0mresult\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mhighlighter\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdoc_list\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mdid\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mquery\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    140\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<string>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: bad operand type for unary -: 'set'"
     ]
    }
   ],
   "source": [
    "searcher = SearcherIIndex('titles.txt')\n",
    "\n",
    "query = '3-0'\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": 71,
   "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",
    "        \"\"\"向索引中添加新文档\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",
    "        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 parse_query(self, doc):\n",
    "        \"\"\"对查询进行自定义解析，保留英文串，对中文串原型插入\n",
    "        \n",
    "        Args:\n",
    "            doc:待解析的原始文档\n",
    "        \n",
    "        Returns:\n",
    "            解析结果列表，元素是带有串类型标记(首字符，e为英文，c为中文)\n",
    "            的切分term结果\n",
    "        \"\"\"\n",
    "        doc = doc.lower() + ' '\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",
    "            flag = None\n",
    "            #增加串标记，e为英文，c为中文(未来可能扩充)\n",
    "            if state_c:\n",
    "                flag = 'e'\n",
    "            else:\n",
    "                flag = 'c'\n",
    "                \n",
    "            if c == ' ':\n",
    "                if state_last != '':\n",
    "                    result.append(cache)\n",
    "                    result.append('s ')\n",
    "                    cache = ''\n",
    "                    state_last = '' \n",
    "            elif c == '(' or c == ')':\n",
    "                if cache != '':\n",
    "                    result.append(cache)\n",
    "                    cache = ''\n",
    "                state_last = ''\n",
    "                result.append('s' + c)\n",
    "            else:\n",
    "                if state_c == state_last:\n",
    "                    cache += c\n",
    "                else:\n",
    "                    if state_last != '':\n",
    "                        result.append(cache)\n",
    "                    cache = flag + c\n",
    "                state_last = state_c\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(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",
    "                cache += all_parts[idx][1:]\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",
    "    \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':\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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'<span style=\"color:red\">华为</span><span style=\"color:red\">Mate30</span>采用安卓系统'"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "searcher = SearcherIIndexVII('titles.txt')\n",
    "searcher.highlighter(\n",
    "    '华为Mate30采用安卓系统','中国华为 mate30')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['c华为', 's ', 'emate30', 's ']\n",
      "(self.term_match('华为')) & self.term_match('mate30') \n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<span style=\"color:red\">华为</span><span style=\"color:red\">Mate30</span>采用安卓系统"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "可安装谷歌gms！<span style=\"color:red\">华为</span><span style=\"color:red\">Mate30</span>确认支持boo"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "iphone11和<span style=\"color:red\">华为</span><span style=\"color:red\">Mate30</span>拍照对比：差距"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"color:red\">华为</span><span style=\"color:red\">Mate30</span>采用安卓系统"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"color:red\">华为</span>发布<span style=\"color:red\">Mate30</span>系列手机：电池最大4500m"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "searcher = SearcherIIndexVII('titles.txt')\n",
    "\n",
    "query = '华为 mate30'\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": 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
}