工程实践善用简单算法，事半功倍。

原创

月小水长

发布于 2024-12-17 16:11:48

1160

文章被收录于专栏：月小水长月小水长

在工程实践中，很多时候写的是纷繁复杂的业务逻辑，在需求急排期短的时候，来不及多想一下，这个需求还有没有更优的解决方案？就匆匆写完仅仅能够完成需求的代码测试通过就上线了

有些时候，业务逻辑如果被高度抽象出来并找到一种类似的经典算法匹配之，不仅代码量少，而且鲁棒性高、且易于维护。

本文将分享这样的一个时刻，抛砖引玉。

需求背景

接到这样一个需求，需要解析用户收藏的 Chrome 书签，并且层次化可视化出来，方便一键触达多层次的书签链接，而不用手动一一展开。

需求分析

我们知道，无论是 Chrome 还是 FireFox，都是允许用户创建多级书签的，意即，根书签栏中的每一个子项，可以是一个具体的书签网址，也可以是下一级书签栏，并且这种层次是可以一直衍生下去的，一位工作了很多年的程序员，他的最大书签栏深度可能达到五六层深度，要触达最深层次的书签地址是比较不直接且伤眼睛的，这就是需求的由来。

首先肯定是要分析书签文件的格式，先在 chrome 浏览器中导出我们自己的书签文件，

打开浏览器书签地址：chrome://bookmarks/
点击页面右上角的三点设置按钮，点击【导出书签】，即可得到一个 html 文件，里面就是书签的保存格式。

层次格式大体如下：

简单总结下书签格式：

每个书签都是一个 DT 元素；
如果书签是具体地址，那么这个 DT 元素下就是一个 A 元素，A 元素的 href 属性就是书签地址，文本内容就是书签名。
否则，DT 元素下就是一个 H3 元素，H3 元素文本内容就是下级书签名；并且这个 DT 元素后紧跟一个 DL 元素，DL 元素下又是很多 DT 元素，又回到第一步。

从格式中可以直观得感觉到这是一个递归问题，事实上也确实如此，只需要一个简单的递归的算法，就能完美解决这个需求中的数据解析问题。

需求实现

由于书签文件内容是 html，计划使用 Python 中的 lxml 库 + xpath 语法。

在开始设计递归算法前，还有一些数据清洗的 dirty works 需要完成，如下：

def get_regular_html():
    with open(bookmark_html_file, mode='r', encoding='utf-8-sig') as fp:
        html_content = fp.read()
    '''
     先规则 html 标签，否则 etree.HTML 解析的结构很混乱
    '''
    html_content = html_content.replace(r'<p>', '')
    html_content = html_content.replace(r'</H3>', r'</H3></DT>')
    html_content = html_content.replace(r'</A>', r'</A></DT>')
    return html_content

主要是去掉一些影响解析的冗余标签，这些是在后面的递归算法设计中才发现问题的，实践是检验真理的唯一标准。

递归算法设计如下：

def parse_html_recursive(root_html):
    children = []
    children_html = root_html.xpath('./child::*')
    for index, ele in enumerate(children_html):
        tag_name = ele.tag.strip()
        if tag_name == 'dt':
            if ele.xpath('./h3'):
                name = ele.xpath('./h3/text()')[0].strip()
                if name in exclude_collection:
                    continue
                children.append({
                    name_key: name,
                    children_key: parse_html_recursive(children_html[index + 1])
                })
            elif ele.xpath('./a'):
                if len(ele.xpath('./a/text()')) == 0:
                    print('过滤掉没有书签名的')
                    continue
                url = ele.xpath('./a/@href')[0]
                name = ele.xpath('./a/text()')[0].strip()
                children.append({
                    name_key: name,
                    url_key: url
                })
    return children

很简洁的思路 + 一些 xpath 语句，基本上是按照书签格式来的，遇到书签地址就解析返回，遇到子书签就递归解析

完整代码如下：

from lxml import etree

import json

bookmark_html_file = 'bookmarks.html'
bookmark_json_file = 'bookmarks.json'


def get_regular_html():
    with open(bookmark_html_file, mode='r', encoding='utf-8-sig') as fp:
        html_content = fp.read()
    '''
     先规则 html 标签，否则 etree.HTML 解析的结构很混乱
    '''
    html_content = html_content.replace(r'<p>', '')
    html_content = html_content.replace(r'</H3>', r'</H3></DT>')
    html_content = html_content.replace(r'</A>', r'</A></DT>')
    return html_content


html = etree.HTML(get_regular_html())

root_name = '书签'
name_key, children_key = 'name', 'children'
url_key = 'url'
bookmark_map_json = {
    name_key: root_name,
}
root = html.xpath('//dl[1]/dl[1]')[0]

# 排除解析的书签文件夹
exclude_collection = ["隐私书签"]


def parse_html_recursive(root_html):
    children = []
    children_html = root_html.xpath('./child::*')
    for index, ele in enumerate(children_html):
        tag_name = ele.tag.strip()
        if tag_name == 'dt':
            if ele.xpath('./h3'):
                name = ele.xpath('./h3/text()')[0].strip()
                if name in exclude_collection:
                    continue
                children.append({
                    name_key: name,
                    children_key: parse_html_recursive(children_html[index + 1])
                })
            elif ele.xpath('./a'):
                if len(ele.xpath('./a/text()')) == 0:
                    print('过滤掉没有书签名的')
                    continue
                url = ele.xpath('./a/@href')[0]
                name = ele.xpath('./a/text()')[0].strip()
                children.append({
                    name_key: name,
                    url_key: url
                })
    return children


bookmark_map_json[children_key] = parse_html_recursive(root)

bookmark_map_json = bookmark_map_json["children"][0]["children"][8]["children"][6]

with open(bookmark_json_file, 'w', encoding='utf-8-sig') as f:
    f.write(json.dumps(bookmark_map_json, indent=2, ensure_ascii=False))

最后解析出来的书签 json 格式如下：

{
  "name": "编程书签",
  "children": [
    {
      "name": "编程书签地址1",
      "url": "https://cloud.tencent.com/developer/article/2443050"
    },
    {
      "name": "编程子书签1",
      "children": [
        {
          "name": "编程书签地址2",
          "url": "https://cloud.tencent.com/developer/article/2275253"
        },
        {
          "name": "编程书签地址3",
          "url": "https://cloud.tencent.com/developer/article/2275249"
        }
      ]
    },
    {
      "name": "编程书签地址4",
      "url": "https://cloud.tencent.com/developer/article/2299508"
    }
  ]
}

非常方便后续的可视化等处理，使用 Echarts 中的 radial-tree 组件就能生成好看实用的树图。