PageSourceSearch

https://www.towdium.me/2019/11/27/pinyin-search-again-5/

html towdium.me collected 2026-10-03 23:20:22 UTC 42,912 bytes, 1,018 lines download raw bytes

1<!DOCTYPE html>
2<html lang="en">
3
4<head>
5    <meta charset="utf-8">
6    <meta http-equiv="X-UA-Compatible" content="IE=edge">
7    <meta name="google-site-verification" content="xBT4GhYoi5qRD5tr338pgPM5OWHHIDR6mNg1a3euekI" />
8    <meta name="viewport" content="width=device-width, initial-scale=1, viewport-fit=cover">
9    <meta name="description" content="这里是 Towdium 的个人博客,分享我的一些学习记录,以及日常的碎碎念">
10    <meta name="keywords"  content="Towdium">
11    <meta name="theme-color" content="#000000">
12    
13    <!-- Open Graph -->
14    <meta property="og:title" content="再谈拼音匹配(五)—— 杂项 - Towdium's here | A personal blog">
15    
16    <meta property="og:type" content="article">
17    <meta property="og:description" content="
18  再谈拼音匹配系列目录:
19第一节 即时匹配与语境
20第二节 传统的字符串索引
21第三节 拼音树(上)
22第四节 拼音树(下)
23第五节 杂项
24
25
26">
27    
28    <meta property="article:published_time" content="2019-11-27T17:42:00Z">
29    
30    
31    <meta property="article:author" content="Towdium">
32    
33    
34    <meta property="article:tag" content="JECh">
35    
36    <meta property="article:tag" content="Java">
37    
38    <meta property="article:tag" content="开发">
39    
40    
41    <meta property="og:image" content="http://towdium.github.io/img/site/avatar.jpg">
42    <meta property="og:url" content="http://towdium.github.io/2019/11/27/pinyin-search-again-5/">
43    <meta property="og:site_name" content="Towdium's here | A personal blog">
44    
45    <title>再谈拼音匹配(五)—— 杂项 - Towdium's here | A personal blog</title>
46
47    <!-- Web App Manifest -->
48    <link rel="manifest" href="/pwa/manifest.json">
49
50    <!-- Favicon -->
51    <link rel="shortcut icon" href="/img/site/favicon.ico">
52    
53    <!-- Canonical URL -->
54    <link rel="canonical" href="https://towdium.github.io/2019/11/27/pinyin-search-again-5/">
55
56    <!-- Bootstrap Core CSS -->
57    <link rel="stylesheet" href="/css/bootstrap.min.css">
58
59    <!-- Custom CSS -->
60    <link rel="stylesheet" href="/css/hux-blog.min.css">
61
62    <!-- Custom Fonts -->
63    <!-- <link href="http://maxcdn.bootstrapcdn.com/font-awesome/4.3.0/css/font-awesome.min.css" rel="stylesheet" type="text/css"> -->
64    <!-- Hux change font-awesome CDN to qiniu -->
65    <link href="//cdnjs.cloudflare.com/ajax/libs/font-awesome/4.6.3/css/font-awesome.min.css" rel="stylesheet" type="text/css">
66
67
68    <!-- HTML5 Shim and Respond.js IE8 support of HTML5 elements and media queries -->
69    <!-- WARNING: Respond.js doesn't work if you view the page via file:// -->
70    <!--[if lt IE 9]>
71        
71<script src="https://oss.maxcdn.com/libs/html5shiv/3.7.0/html5shiv.js"></script>
71
72        
72<script src="https://oss.maxcdn.com/libs/respond.js/1.4.2/respond.min.js"></script>
72
73    <![endif]-->
74
75    <!-- ga & ba script hoook -->
76    
76<script></script>
76
77</head>
78
79
80<!-- hack iOS CSS :active style -->
81<body ontouchstart="">
82
83    <!-- Navigation -->
84
85<nav class="navbar navbar-default navbar-custom navbar-fixed-top">
86
87    <div class="container-fluid">
88        <!-- Brand and toggle get grouped for better mobile display -->
89        <div class="navbar-header page-scroll">
90            <button type="button" class="navbar-toggle">
91                <span class="sr-only">Toggle navigation</span>
92                <span class="icon-bar"></span>
93                <span class="icon-bar"></span>
94                <span class="icon-bar"></span>
95            </button>
96            <a class="navbar-brand" href="/">Towdium's here</a>
97        </div>
98
99        <!-- Collect the nav links, forms, and other content for toggling -->
100        <div id="huxblog_navbar">
101            <div class="navbar-collapse">
102                <ul class="nav navbar-nav navbar-right">
103                    <li>
104                        <a href="/">Home</a>
105                    </li>
106                    
107                    
108                    
109                    
110                    <li>
111                        <a href="/about/">About</a>
112                    </li>
113                    
114                    
115                    
116                    <li>
117                        <a href="/api/">API</a>
118                    </li>
119                    
120                    
121                    
122                    <li>
123                        <a href="/archive/">Archive</a>
124                    </li>
125                    
126                    
127                    
128                    
129                    
130                    
131                    
132                    
133                    
134                    
135                    
136                    
137                    
138                    
139                    
140                    
141                    
142                    
143                </ul>
144            </div>
145        </div>
146        <!-- /.navbar-collapse -->
147    </div>
148    <!-- /.container -->
149</nav>
150<script>
151    // Drop Bootstarp low-performance Navbar
152    // Use customize navbar with high-quality material design animation
153    // in high-perf jank-free CSS3 implementation
154    var $body   = document.body;
155    var $toggle = document.querySelector('.navbar-toggle');
156    var $navbar = document.querySelector('#huxblog_navbar');
157    var $collapse = document.querySelector('.navbar-collapse');
158
159    var __HuxNav__ = {
160        close: function(){
161            $navbar.className = " ";
162            // wait until animation end.
163            setTimeout(function(){
164                // prevent frequently toggle
165                if($navbar.className.indexOf('in') < 0) {
166                    $collapse.style.height = "0px"
167                }
168            },400)
169        },
170        open: function(){
171            $collapse.style.height = "auto"
172            $navbar.className += " in";
173        }
174    }
175
176    // Bind Event
177    $toggle.addEventListener('click', function(e){
178        if ($navbar.className.indexOf('in') > 0) {
179            __HuxNav__.close()
180        }else{
181            __HuxNav__.open()
182        }
183    })
184
185    /**
186     * Since Fastclick is used to delegate 'touchstart' globally
187     * to hack 300ms delay in iOS by performing a fake 'click',
188     * Using 'e.stopPropagation' to stop 'touchstart' event from 
189     * $toggle/$collapse will break global delegation.
190     * 
191     * Instead, we use a 'e.target' filter to prevent handler
192     * added to document close HuxNav.  
193     *
194     * Also, we use 'click' instead of 'touchstart' as compromise
195     */
196    document.addEventListener('click', function(e){
197        if(e.target == $toggle) return;
198        if(e.target.className == 'icon-bar') return;
199        __HuxNav__.close();
200    })
201</script>
201
202
203
204    <!-- Image to hack wechat -->
205<!-- <img src="/img/site/icon.png" width="0" height="0"> -->
206<!-- <img src="/https://api.towdium.me/unsplash/source/collection/645108/2600x500" width="0" height="0"> -->
207
208<!-- Post Header -->
209
210
211
212<style type="text/css">
213    header.intro-header{
214        position: relative;
215        background-image: url('https://api.towdium.me/unsplash/source/collection/645108/2600x500');
216        background: ;
217    }
218
219    
220</style>
221
222<header class="intro-header" >
223
224<div style="background: rgba(0, 0, 0,0.5);">
225    <div class="header-mask"></div>
226    
227    <div class="container">
228        <div class="row">
229            <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
230                <div class="post-heading">
231                    <div class="tags">
232                        
233                        <a class="tag" href="/archive/?tag=JECh" title="JECh">JECh</a>
234                        
235                        <a class="tag" href="/archive/?tag=Java" title="Java">Java</a>
236                        
237                        <a class="tag" href="/archive/?tag=%E5%BC%80%E5%8F%91" title="开发">开发</a>
238                        
239                    </div>
240                    <h1>再谈拼音匹配(五)—— 杂项</h1>
241                    
242                    <h2 class="subheading"></h2>
243                    <span class="meta">Posted by Towdium on November 27, 2019</span>
244                </div>
245            </div>
246        </div>
247    </div>
248</div>
249</header>
250
251
252
253
254
255
256<!-- Post Content -->
257<article>
258    <div class="container">
259        <div class="row">
260
261    <!-- Post Container -->
262            <div class="
263                col-lg-8 col-lg-offset-2
264                col-md-10 col-md-offset-1
265                post-container">
266
267                <!-- Multi-Lingual -->
268                
269
270                <blockquote>
271  <p>再谈拼音匹配系列目录:<br />
272<a href="https://www.towdium.me/2019/11/05/pinyin-search-again-1/">第一节 即时匹配与语境</a><br />
273<a href="https://www.towdium.me/2019/11/10/pinyin-search-again-2/">第二节 传统的字符串索引</a><br />
274<a href="https://www.towdium.me/2019/11/17/pinyin-search-again-3/">第三节 拼音树(上)</a><br />
275<a href="https://www.towdium.me/2019/11/20/pinyin-search-again-4/">第四节 拼音树(下)</a><br />
276第五节 杂项</p>
277</blockquote>
278
279<blockquote>
280  <p>所有内容的实现细节参见 <a href="https://github.com/Towdium/PinIn">PinIn</a></p>
281</blockquote>
282
283<h2 id="前言">前言</h2>
284
285<p>在啰嗦了两节之后,我们终于介绍完了拼音树相关的内容。这一节作为整个系列的结束,我会把剩下的内容全部填完,这其中包括了拼音树以外的搜索结构,各类结构的性能测试,被废弃的设计还有潜在的开发方向。</p>
286
287<h2 id="其他搜索结构">其他搜索结构</h2>
288
289<p>对我而言,拼音树的性能毫无疑问已经让我足够满意了。但是他在各项数据上仍然算不上极致:对于索引构建,他要花费数倍于哈希表的时间;对于搜索,使用较短的搜索串时,相比起单纯将结果添加入哈希表,它的耗时要多出数倍,而使用较长的搜索串时,尽管结果通常更少,但是耗时约和短搜索串相当;对于内存消耗,它要花费数倍于字符串本身的容量。尽管对于拼音搜索而言,这样的结果已经是非常可观了,但是在极端情况下,使用仍然会受到限制。因此,这里还有更多的搜索结构可供使用。我这里并不将这些结构称为索引,因为他们的开发过于侧重工程上的优化,所以非常简单粗暴。但是你也知道,在极端场景下,理论模型往往受到各种条件的制约,工程上的优化则显得格外重要。</p>
290
291<h4 id="simplesearcher">SimpleSearcher</h4>
292
293<p>正如它的名字,这个搜索结构简直就是简单到令人发指:我们将所有字符串存储起来,在需要使用时遍历搜索并返回结果。不过,既然我把它实现出来,自然有他存在的意义。首先,我们不需要建立各种复杂的树结构,所以它在构造上要比拼音树快出几倍。其次,他不需要占用内容用于缓存,所以他占用的内存也是小到极致。换句话说,他几乎是你所能用到的构建最快,占用内存最少的搜索结构。</p>
294
295<p>除去这些显而易见的特征,他还利用了前文所述的“外部加速”和“切片策略”。这使得它在搜索时使用的时间大约只有遍历æ
295œç´¢çš„三分之一,而用于字符串存储的内存使用仅为通用容器的一半。而且,如前文所述,所有的搜索结构在执行搜索时返回的结果都会按插入时的顺序排列。这一特性对于一些涉及到优先级和排序的场景可能很有帮助。</p>
296
297<h4 id="cachedsearcher">CachedSearcher</h4>
298
299<p>前文中我们提到倒排索引会遭遇组合困境,所以建立完整的倒排索引并不现实。除去大量组合带来的内存开销,建立索引时遍历所有的搜索串同样极为耗时。假设我们使用遍历搜索串来建立缓存,并且只对 26 个小写字母建立 3 位的缓存,我们就需要执行将近两万次搜索。即使每次搜索耗时 1ms,完全建立缓存所需的时间将近 20 秒。作为参考,对于这个容量的数据,建立拼音树所需的时间大约是 100ms。</p>
300
301<p>但是我们换个思路,不同于主动地遍历搜索串,我们只对搜索结果进行被动缓存:在第一次搜索时执行遍历搜索,接下来则使用缓存的结果。和相当多的缓存结构相同,我们不可能对结果无穷无尽地进行缓存,否则我们仍然会面对内存爆炸的困境。取而代之是,我们对缓存限定一个容量,超过容量则将最早使用的条目移除(LRU)。</p>
302
303<p>如果我们想要索引对结果有更加灵活的反应,page flooding 带来的影响就难以避免。举个例子,假如我们的缓存容量只有十个条目,我们只需要连续搜索一大堆又长又罕见的词条,就可以用垃圾内容塞满缓存;如果我们用一些稳健的策略(例如LFU),结果就是缓存一旦填满,新的内容就很难进入,这对于容量很小的缓存而言同样不合适。根本而言,我们需要做的是从源头上堵截垃圾内容进入,这里的策略就是限制缓存搜索串的长度。</p>
304
305<p>你可能有点疑惑,如果我们只缓存短串的结果,那么对于长串是不是就毫无帮助呢?当然不是,否则这个缓存结构的存在就毫无意义。对于文本匹配我们有这一结论:如果 a 是 b 的子串,b 是 c 的子串,则 a 是 c 的子串。对于拼音搜索,我对算法进行了轻度的魔改,使得它满足这一条件:如果 a 是 b 的前缀,拼音 b 匹配文本 c,则拼音 a 匹配文本 c。这是我在之前的文章里反复讨论过的思路:由于这个关系,只要 a 是 b 的前缀,则 b 的搜索结果的集合必然是 a 的结果的子集。这里我们暂且称之为“渐进特性”。基于这一特性,当我们搜索一个长串时,只需要寻找它前缀所对应结果的集合,再对这个集合内的条目(而不是总集)进行遍历搜索即可。</p>
306
307<p>这一思路听起来不是特别诱人,但是对于三个字符长度的搜索串,匹配的结果很有可能只是总集的百分之一。也就是说对于所有更长的搜索串,比起对总集执行遍历搜索,这个缓存有可能将性能提升一百倍。这实际上借鉴了 q-gram 的思想:任意的字符可能是非常常见的,但是稍长一些的序列就会变得罕见得多。为了更高效地使用缓存,我们对缓存串的长度限制是非常严格的。尽管缓存容量是通过一些数学关系表达的,但是对于所有的前缀匹配和绝大部分的包含匹配,缓存总容量应该在 200 条目以下,每个条目被限制在 3 个字符以内。只有对相当长的文本进行包含搜索时,缓存容量才会有明显增长,并且允许 4 个字符长的缓存条目。整体而言,缓存的空间复杂度于拼音树一致,并且实际内存消耗被控制在略小于拼音树总容量的程度。同时,缓存容量也可以被手动修改以适用于不同的场景。</p>
308
309<p>由于这个缓存的生成是完全被动的,一个显而易见的优势就是它构造极快。除此之外,当缓存内容预热完成,它的搜索速度也并不会落后拼音树太多。但是在预热不完全或者缓存不足时,由于它在执行搜索之前还要ç”
309Ÿæˆå¯¹åº”的缓存内容,搜索速度实际上要比 <code class="language-plaintext highlighter-rouge">SimpleSeacher</code> 更慢,和未加速的遍历搜索相近。从我的个人角度而言,如果对索引建立的耗时没有极端要求,由于缓存不确定造成的性能不稳定,我建议直接使用拼音树 <code class="language-plaintext highlighter-rouge">TreeSearcher</code> 作为通用的解决方案。值得一提的是,缓存的实现可以被轻松修改以解除条目的长度限制,这对于极少数条目极高频的查询可能有奇效,但是考虑到该场景更加极端,我们这里就不讨论了。</p>
310
311<h2 id="性能测试">性能测试</h2>
312
313<p>测试使用两组数据。第一组提取自 Enigmatica 模组包,可以近似模拟极端条件下的 Minecraft 环境,文本文件 902KB,共 37k 词条,424k 字符。第二组提取自腾讯 AILab 的汉语短语 <a href="https://ai.tencent.com/ailab/nlp/embedding.html">语料库</a>,文本文件 14.4MB,共 1M 词条,4.81M 字符。测试在 i7-7700HQ 上进行,仅使用单核运算。对于每组文本,我们分别测量了用于前缀匹配与用于包含匹配的两组时间数据。对于全文匹配,性能几乎等同于前缀匹配,我这里就不单独列出了。</p>
314
315<p><strong>小数据集 + 包含匹配</strong></p>
316
317<table>
318  <thead>
319    <tr>
320      <th style="text-align: center">匹配逻辑</th>
321      <th style="text-align: center">构建耗时</th>
322      <th style="text-align: center">预热耗时</th>
323      <th style="text-align: center">搜索耗时</th>
324      <th>内存使用</th>
325    </tr>
326  </thead>
327  <tbody>
328    <tr>
329      <td style="text-align: center">TreeSearcher</td>
330      <td style="text-align: center">210ms</td>
331      <td style="text-align: center">N/A</td>
332      <td style="text-align: center">0.19ms</td>
333      <td>9.50MB</td>
334    </tr>
335    <tr>
336      <td style="text-align: center">SimpleSearcher</td>
337      <td style="text-align: center">27ms</td>
338      <td style="text-align: center">N/A</td>
339      <td style="text-align: center">9.1ms</td>
340      <td>1.84MB</td>
341    </tr>
342    <tr>
343      <td style="text-align: center">CachedSearcher</td>
344      <td style="text-align: center">28ms</td>
345      <td style="text-align: center">16ms</td>
346      <td style="text-align: center">0.55ms</td>
347      <td>见备注</td>
348    </tr>
349    <tr>
350      <td style="text-align: center">遍历拼音匹配</td>
351      <td style="text-align: center">N/A</td>
352      <td style="text-align: center">N/A</td>
353      <td style="text-align: center">23ms</td>
354      <td>N/A</td>
355    </tr>
356    <tr>
357      <td style="text-align: center">遍历 contains</td>
358      <td style="text-align: center">N/A</td>
359      <td style="text-align: center">N/A</td>
360      <td style="text-align: center">0.53ms</td>
361      <td>N/A</td>
362    </tr>
363  </tbody>
364</table>
365
366<p><strong>小数据集 + 前缀匹配</strong></p>
367
368<table>
369  <thead>
370    <tr>
371      <th style="text-align: center">匹配逻辑</th>
372      <th style="text-align: center">构建耗时</th>
373      <th style="text-align: center">预热耗时</th>
374      <th style="text-align: center">搜索耗时</th>
375      <th style="text-align: center">内存使用</th>
376    </tr>
377  </thead>
378  <tbody>
379    <tr>
380      <td style="text-align: center">TreeSearcher</td>
381      <td style="text-align: center">62.5ms</td>
382      <td style="text-align: center">N/A</td>
383      <td style="text-align: center">0.083ms</td>
384      <td style="text-align: center">2.80MB</td>
385    </tr>
386    <tr>
387      <td style="text-align: center">SimpleSearcher</td>
388      <td style="text-align: center">30ms</td>
389      <td style="text-align: center">N/A</td>
390      <td style="text-align: center">2.4ms</td>
391      <td style="text-align: center">1.84MB</td>
392    </tr>
393    <tr>
394      <td style="text-align: center">CachedSearcher</td>
395      <td style="text-align: center">28ms</td>
396      <td style="text-align: center">2.8ms</td>
397      <td style="text-align: center">0.10ms</td>
398      <td style="text-align: center">见备注</td>
399    </tr>
400    <tr>
401      <td style="text-align: center">遍历拼音匹配</td>
402      <td style="text-align: center">N/A</td>
403      <td style="text-align: center">N/A</td>
404      <td style="text-align: center">8.8ms</td>
405      <td style="text-align: center">N/A</td>
406    </tr>
407    <tr>
408      <td style="text-align: center">遍历 startsWith</td>
409      <td style="text-align: center">N/A</td>
410      <td style="text-align: center">N/A</td>
411      <td style="text-align: center">0.53ms</td>
412      <td style="text-align: center">N/A</td>
413    </tr>
414  </tbody>
415</table>
416
417<p><strong>大数据集 + 包含匹配</strong></p>
418
419<table>
420  <thead>
421    <tr>
422      <th style="text-align: center">匹配逻辑</th>
423      <th style="text-align: center">构建耗时</th>
424      <th style="text-align: center">预热耗时</th>
425      <th style="text-align: center">搜索耗时</th>
426      <th style="text-align: center">内存使用</th>
427    </tr>
428  </thead>
429  <tbody>
430    <tr>
431      <td style="text-align: center">TreeSearcher</td>
432      <td style="text-align: center">5000ms</td>
433      <td style="text-align: center">N/A</td>
434      <td style="text-align: center">0.66ms</td>
435      <td style="text-align: center">159MB</td>
436    </tr>
437    <tr>
438      <td style="text-align: center">SimpleSearcher</td>
439      <td style="text-align: center">120ms</td>
440      <td style="text-align: center">N/A</td>
441      <td style="text-align: center">200ms</td>
442      <td style="text-align: center">22.8MB</td>
443    </tr>
444    <tr>
445      <td style="text-align: center">CachedSearcher</td>
446      <td style="text-align: center">150ms</td>
447      <td style="text-align: center">260ms</td>
448      <td style="text-align: center">6.5ms</td>
449      <td style="text-align: center">见备注</td>
450    </tr>
451    <tr>
452      <td style="text-align: center">遍历拼音匹配</td>
453      <td style="text-align: center">N/A</td>
454      <td style="text-align: center">N/A</td>
455      <td style="text-align: center">430ms</td>
456      <td style="text-align: center">N/A</td>
457    </tr>
458    <tr>
459      <td style="text-align: center">遍历 contains</td>
460      <td style="text-align: center">N/A</td>
461      <td style="text-align: center">N/A</td>
462      <td style="text-align: center">12ms</td>
463      <td style="text-align: center">N/A</td>
464    </tr>
465  </tbody>
466</table>
467
468<p><strong>大数据集 + 前缀匹配</strong></p>
469
470<table>
471  <thead>
472    <tr>
473      <th style="text-align: center">匹配逻辑</th>
474      <th style="text-align: center">构建耗时</th>
475      <th style="text-align: center">预热耗时</th>
476      <th style="text-align: center">搜索耗时</th>
477      <th style="text-align: center">内存使用</th>
478    </tr>
479  </thead>
480  <tbody>
481    <tr>
482      <td style="text-align: center">TreeSearcher</td>
483      <td style="text-align: center">1300ms</td>
484      <td style="text-align: center">N/A</td>
485      <td style="text-align: center">0.42ms</td>
486      <td style="text-align: center">70.4MB</td>
487    </tr>
488    <tr>
489      <td style="text-align: center">SimpleSearcher</td>
490      <td style="text-align: center">120ms</td>
491      <td style="text-align: center">N/A</td>
492      <td style="text-align: center">48ms</td>
493      <td style="text-align: center">22.8MB</td>
494    </tr>
495    <tr>
496      <td style="text-align: center">CachedSearcher</td>
497      <td style="text-align: center">150ms</td>
498      <td style="text-align: center">64ms</td>
499      <td style="text-align: center">1.8ms</td>
500      <td style="text-align: center">见备注</td>
501    </tr>
502    <tr>
503      <td style="text-align: center">遍历拼音匹配</td>
504      <td style="text-align: center">N/A</td>
505      <td style="text-align: center">N/A</td>
506      <td style="text-align: center">120ms</td>
507      <td style="text-align: center">N/A</td>
508    </tr>
509    <tr>
510      <td style="text-align: center">遍历 startsWith</td>
511      <td style="text-align: center">N/A</td>
512      <td style="text-align: center">N/A</td>
513      <td style="text-align: center">10ms</td>
514      <td style="text-align: center">N/A</td>
515    </tr>
516  </tbody>
517</table>
518
519<blockquote>
520  <p>备注:<code class="language-plaintext highlighter-rouge">CachedSearcher</code> 的内存占用在不同的场景下会有明显波动,在绝大部分情况下小于 <code class="language-plaintext highlighter-rouge">TreeSearcher</code> 的用量。</p>
521</blockquote>
522
523<p>
523需要注意的是,所有搜索结构的内存使用值均包含所有文本,一般情况下使用者无需额外消耗内存进行存储。对于小数据集,使用 <code class="language-plaintext highlighter-rouge">ArrayList&lt;String&gt;</code> 存储文本约占用 2.6MB 内存,而大数据集约占用 56MB 内存。</p>
524
525<p>尽管我们在讨论拼音索引的性能时,常常拿它与输入法相比,但是从本质上而言,其中涉及到的概念是完全不同的:</p>
526
527<ul>
528  <li>相当多的输入法使用数据库进行搜索,或者使用其他方法将缓存内容存储在硬盘上,从而减少内存消耗。因此,有些输入法有可能占用上百 MB 的硬盘空间。</li>
529  <li>输入法执行的是全文匹配,也就是说输入“zhong”时,不可能联想到“中国”。这种匹配模式更加苛刻,因此可以有更多方法来优化执行速度。</li>
530  <li>对于相当多数输入法,短语的发音在词库中是确定的,也就是说输入“huoping”并不会联想到“和平”。这在很大程度上解决了多音字的混合问题,而在运行时我们几乎无法完全正确地确定多音字的发音。</li>
531  <li>几乎所有输入法都依赖于搜索串的切分,这对于简化单词搜索内容极为有利。对于支持中英混输的输入法,很有可能在切分时预先参考了英文词库(例如匹配公共子串)。而在我们的场景下,我们无法将词条中的英文部分单独切分出来,因而分词会变得极为繁琐。</li>
532  <li>输入法可以对词库进行相当复杂的预处理,并将结果持久化,而我们的场景要求所有操作在运行时在内存中完成。一个显而易见的例子就是 Rime 可以使用相当大的静态词库,但是当用户(动态)词库容量稍大时就有可能带来性能问题。</li>
533</ul>
534
535<p>由于以上的各类原因,我们所面对的性能压力实际上远高于输入法。对于输入法而言,拼音匹配的逻辑只能算得上是基石,而核心则是各种语言模型。而这个项目则是完全侧重于极端场景下的性能。通过测试数据你也能看出来,在各项性能指标上可以压缩的空间已经是非常小了。</p>
536
537<h2 id="反思与计划">反思与计划</h2>
538
539<p>如果你很熟悉 JECh 这个项目的话,你可能知道截至目前索引结构已经迭代到第三个大版本了。第一个版本继承自 JEI,使用缓存加实时搜索。这个版本和目前的 CachedSearcher 很接近,但是对缓存中搜索串的长度不加限制。在绝大部分场景下,它的性能都勉强可用,但是在预热阶段或者执行高频搜索时会产生卡顿。第二个版本使用了一个巨大的缓存,将任何搜索过的搜索串和索引串组合产生的结果完全缓存下来。这个结构是完全失败的:它不仅占用相当多的内存,同时在搜索性能上也并没有明显的提升。每次搜索时,我们都要在缓存中遍历查找所有索引串对应的结果,而这一操作并不比遍历匹配快太多。我曾经因此吐槽过 HashMap 的性能,但是这一问题的瓶颈实际上不在 HashMap,而在缓存设计本身。不过话又说回来,目前该项目中广泛使用的外部加速机制和这一设计非常接近,但是它不仅有着更加谨慎的性能优化,而且从设计上在泛用性和利用率上具有决定性的优势。</p>
540
541<p>相比起之前的方案,目前基于拼音树的实现在整体上更加平衡且高效,唯一令人担心的部分就是相比起不需要建立的搜索结构,它在缓存构建上耗时稍多。在之前版本的 MC 中,缓存构造是在游戏启动前执行的,相比起动辄十几二十分钟的启动时间,这几秒钟完全可以忽略不计。而在新版本的 MC 中,相关的操作被移动到了加载世界的环节。尽管在绝大部分情况下建立索引只需要 5 秒以下的时间,我们仍然需要在性能问题上保持关注。</p>
542
543<p>说到索引构造的性能问题,这个项目中使用的后缀数实现实际上是非常粗糙的。在构造环节,不同于大部分性能优化过的实现,他实际上仅仅是将一个字符串的所有后缀顺序加入字典树。我原先认为这应该就是所谓的 $n^2$ 暴力构造,但是测试下来它的性能近似在 $n$ 和 $nlogn$ 之间。得益于压缩树的切片èŠ
543‚点,在插入条目时,一旦我们在树结构中移动到顶端,就可以直接插入一个切片节点来指代剩下的所有内容。也就是说,插入条目的性能主要受到树层数的限制。这显然要慢于各类线性构造的算法,但是大部分线性构造算法需要维护 suffix link,分离节点和边,这需要占用更多内存,而且也不适用于密集节点,所以应用这些算法可能会使内存占用翻倍甚至增加数倍。考虑到这些因素,目前在这方面并没有改动的计划。</p>
544
545<h2 id="小结">小结</h2>
546
547<p>说到这里,我们这个系列就告一段落了。对于拼音环境下的字串查找问题,我们给出了实时匹配的实现,基于后缀数的拼音树的实现,以及两种在实时匹配上加速的实现。尽管在性能上还存在一些优化的空间,我想它应该可以应对大部分场景了。如果整个系统有什么新的改动,我也会以附言的形式进行更新。那么,我们下次见吧,</p>
548
549
550                
551                <div class="copyright">
552                    <p align = "center" >
553                        <font size="2.5px", color="grey">
554                        若非特殊注明,文章均为博主原创,通过 CC 4.0 BY License 授权转载
555                        </font>
556                    </p>
557                </div>
558
559                <hr style="visibility: hidden;">
560                <ul class="pager">
561                    
562                    <li class="previous">
563                        <a href="/2019/11/20/pinyin-search-again-4/" data-toggle="tooltip" data-placement="top" title="再谈拼音匹配(四)—— 拼音树(下)">
564                        Previous<br>
565                        <span>再谈拼音匹配(四)—— 拼音树(下)</span>
566                        </a>
567                    </li>
568                    
569                    
570                    <li class="next">
571                        <a href="/2019/12/08/algorithm-array-rotation/" data-toggle="tooltip" data-placement="top" title="从费马小定理到数组旋转">
572                        Next<br>
573                        <span>从费马小定理到数组旋转</span>
574                        </a>
575                    </li>
576                    
577                </ul>
578                <hr style="visibility: hidden;">
579
580                
581                <!-- disqus 评论框 start -->
582                <div class="comment">
583                    <div id="disqus_thread" class="disqus-thread"></div>
584                </div>
585                <!-- disqus 评论框 end -->
586                
587
588                
589            </div>  
590
591    <!-- Side Catalog Container -->
592        
593            <div class="
594                col-lg-2 col-lg-offset-0
595                visible-lg-block
596                sidebar-container
597                catalog-container">
598                <div class="side-catalog">
599                    <hr class="hidden-sm hidden-xs">
600                    <h5>
601                        <a class="catalog-toggle" href="#">CATALOG</a>
602                    </h5>
603                    <ul class="catalog-body"></ul>
604                </div>
605            </div>
606        
607
608    <!-- Sidebar Container -->
609            <div class="
610                col-lg-8 col-lg-offset-2
611                col-md-10 col-md-offset-1
612                sidebar-container">
613
614                <!-- Featured Tags -->
615                
616
617
618<section>
619    
620        <hr class="hidden-sm hidden-xs">
621    
622    <h5><a href="/archive/">FEATURED TAGS</a></h5>
623    <div class="tags">
624        
625        
626        
627        </a>
628        
629        
630                <a data-sort="0029" 
631                    href="/archive/?tag=%E6%97%A5%E5%B8%B8"
632                    title="日常"
633                    rel="8">日常</a>
634        
635                <a data-sort="0024" 
636                    href="/archive/?tag=Java"
637                    title="Java"
638                    rel="13">Java</a>
639        
640                <a data-sort="0030" 
641                    href="/archive/?tag=%E5%BC%80%E5%8F%91"
642                    title="开发"
643                    rel="7">开发</a>
644        
645                <a data-sort="0030" 
646                    href="/archive/?tag=JECh"
647                    title="JECh"
648                    rel="7">JECh</a>
649        
650                <a data-sort="0031" 
651                    href="/archive/?tag=Atom"
652                    title="Atom"
653                    rel="6">Atom</a>
654        
655                <a data-sort="0031" 
656                    href="/archive/?tag=LaTeX"
657                    title="LaTeX"
658                    rel="6">LaTeX</a>
659        
660                <a data-sort="0034" 
661                    href="/archive/?tag=%E7%BD%91%E7%BB%9C"
662                    title="网络"
663                    rel="3">网络</a>
664        
665                <a data-sort="0035" 
666                    href="/archive/?tag=C"
667                    title="C"
668                    rel="2">C</a>
669        
670                <a data-sort="0035" 
671                    href="/archive/?tag=Jekyll"
672                    title="Jekyll"
673                    rel="2">Jekyll</a>
674        
675                <a data-sort="0035" 
676                    href="/archive/?tag=OOP"
677                    title="OOP"
678                    rel="2">OOP
679    </div>
680</section>
681
682
683                <!-- Friends Blog -->
684                
685<hr>
686<h5>FRIENDS</h5>
687<ul class="list-inline">
688  
689  <li><a href="http://shellcottage.me/">Shell Cottage</a></li>
690  
691  <li><a href="https://tartaricacid.github.io/">酒石酸菌</a></li>
692  
693</ul>
694
695            </div>
696        </div>
697    </div>
698</article>
699
700<!-- add support for mathjax by voleking-->
701  
701<script type="text/x-mathjax-config">
702  MathJax.Hub.Config({
703    "fast-preview": {disabled: true},
704    tex2jax: {preview: "none"},
705    CommonHTML: { linebreaks: { automatic: true } },
706    SVG: { linebreaks: { automatic: true } },
707    "TeX": {
708      equationNumbers: {autoNumber: ["none"]},
709      Macros: {
710        AA : "{\\unicode{x212B}}",
711        oiiint : "{\\rlap{\\subset}\\mkern-0.11em\\rlap\\int\\mkern0.3em\\rlap\\int\\mkern0.14em\\int\\mkern-1.1em\\supset}",
712        oiint : "{\\subset\\hspace{-11pt}\\iint\\hspace{-11pt}\\supset}"
713      }
714    },
715    "HTML-CSS": {
716        scale: 90,
717        linebreaks: { automatic: true }
718      },
719    "tex2jax": {
720        inlineMath: [ ['$','$'], ["\\(","\\)"] ],
721        processEscapes: true
722      }
723  });
724  
725  MathJax.Hub.Register.StartupHook("Begin",function () {
726    MathJax.Hub.Queue(function () {
727      var math = document.getElementById("rescale");
728      var w = math.offsetWidth, W = math.parentNode.offsetWidth-40;
729      if (w > W) {
730        math.style.fontSize = (95*W/w)+"%";
731        MathJax.Hub.getAllJax(math)[0].Rerender();
732      }
733    });
734  });
735  </script>
vendor: 1 bytes, line 735
735
736<script type="text/javascript"
737        src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
738</script>
738
739
740
741
742
743
744<!-- disqus 公共JS代码 start (一个网页只需插入一次) -->
745<script type="text/javascript">
746    /* * * CONFIGURATION VARIABLES * * */
747    var disqus_shortname = "towdium";
748    var disqus_identifier = "/2019/11/27/pinyin-search-again-5";
749    var disqus_url = "http://towdium.github.io/2019/11/27/pinyin-search-again-5/";
750
751    (function() {
752        var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
753        dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
754        (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
755    })();
756</script>
756
757<!-- disqus 公共JS代码 end -->
758
759
760
761
762<!-- async load function -->
763<script>
764    function async(u, c) {
765      var d = document, t = 'script',
766          o = d.createElement(t),
767          s = d.getElementsByTagName(t)[0];
768      o.src = u;
769      if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
770      s.parentNode.insertBefore(o, s);
771    }
772</script>
772
773<!-- anchor-js, Doc:http://bryanbraun.github.io/anchorjs/ -->
774<script>
775    async("//cdnjs.cloudflare.com/ajax/libs/anchor-js/1.1.1/anchor.min.js",function(){
776        anchors.options = {
777          visible: 'hover',
778          placement: 'right',
779          // icon: '#'
780        };
781        anchors.add().remove('.intro-header h1').remove('.subheading').remove('.sidebar-container h5');
782    })
783</script>
783
784<style>
785    /* place left on bigger screen */
786    @media all and (min-width: 800px) {
787        .anchorjs-link{
788            position: absolute;
789            left: -0.75em;
790            font-size: 1.1em;
791            margin-top : -0.1em;
792        }
793    }
794</style>
795
796
797
798    <!-- Footer -->
799<footer>
800    <div class="container">
801        <div class="row">
802            <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
803                <!-- SNS Link -->
804                
805
806
807<ul class="list-inline text-center">
808
809
810  
811  <li>
812    <a href="/feed.xml">
813      <span class="fa-stack fa-lg">
814        <i class="fa fa-circle fa-stack-2x"></i>
815        <i class="fa fa-rss fa-stack-1x fa-inverse"></i>
816      </span>
817    </a>
818  </li>
819  
820  
821  
822  
823  <li>
824    <a target="_blank" href="http://weibo.com/5092127194">
825      <span class="fa-stack fa-lg">
826        <i class="fa fa-circle fa-stack-2x"></i>
827        <i class="fa fa-weibo fa-stack-1x fa-inverse"></i>
828      </span>
829    </a>
830  </li>
831  
832  
833  
834  <li>
835    <a target="_blank" href="https://github.com/towdium">
836      <span class="fa-stack fa-lg">
837        <i class="fa fa-circle fa-stack-2x"></i>
838        <i class="fa fa-github fa-stack-1x fa-inverse"></i>
839      </span>
840    </a>
841  </li>
842  
843  
844</ul>
845
846                <p class="copyright text-muted">
847                    Copyright &copy; Towdium's here 2022
848                    <br>
849                    Powered by <a href="http://huangxuan.me">Hux Blog</a> |
850                    <iframe
851                        style="margin-left: 2px; margin-bottom:-5px;"
852                        frameborder="0" scrolling="0" width="100px" height="20px"
853                        src="https://ghbtns.com/github-btn.html?user=huxpro&repo=huxpro.github.io&type=star&count=true" >
854                    </iframe>
855                </p>
856            </div>
857        </div>
858    </div>
859</footer>
860
861<!-- jQuery -->
862<script src="/js/jquery.min.js "></script>
862
863
864<!-- Bootstrap Core JavaScript -->
865<!-- Currently, only navbar scroll-down effect at desktop still depends on this -->
866<script src="/js/bootstrap.min.js "></script>
866
867
868<!-- Custom Theme JavaScript -->
869<script src="/js/hux-blog.min.js "></script>
869
870
871<!-- Service Worker -->
872
873<script src="/js/snackbar.js "></script>
vendor: 1 bytes, line 873
873
874<script src="/js/sw-registration.js "></script>
874
875
876
877<!-- async load function -->
878<script>
879    function async(u, c) {
880      var d = document, t = 'script',
881          o = d.createElement(t),
882          s = d.getElementsByTagName(t)[0];
883      o.src = u;
884      if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
885      s.parentNode.insertBefore(o, s);
886    }
887</script>
887
888
889<!--
890     Because of the native support for backtick-style fenced code blocks
891     right within the Markdown is landed in Github Pages,
892     From V1.6, There is no need for Highlight.js,
893     so Huxblog drops it officially.
894
895     - https://github.com/blog/2100-github-pages-now-faster-and-simpler-with-jekyll-3-0
896     - https://help.github.com/articles/creating-and-highlighting-code-blocks/
897     - https://github.com/jneen/rouge/wiki/list-of-supported-languages-and-lexers
898-->
899<!--
900    
900<script>
901        async("http://cdn.bootcss.com/highlight.js/8.6/highlight.min.js", function(){
902            hljs.initHighlightingOnLoad();
903        })
904    </script>
904
905    <link href="http://cdn.bootcss.com/highlight.js/8.6/styles/github.min.css" rel="stylesheet">
906-->
907
908
909
910
911
912<!--fastClick.js -->
913<script>
914    async("//cdnjs.cloudflare.com/ajax/libs/fastclick/1.0.6/fastclick.min.js", function(){
915        var $nav = document.querySelector("nav");
916        if($nav) FastClick.attach($nav);
917    })
918</script>
918
919
920
921<!-- Google Analytics -->
922
923<script>
924    // dynamic User by Hux
925    var _gaId = 'UA-73095900-1';
926    var _gaDomain = 'www.towdium.me';
927
928    // Originial
929    (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
930    (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
931    m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
932    })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
933
934    ga('create', _gaId, _gaDomain);
935    ga('send', 'pageview');
936</script>
936
937
938
939
940<!-- Baidu Tongji -->
941
942
943
944<!-- Side Catalog -->
945
946<script type="text/javascript">
947    function generateCatalog (selector) {
948
949        // interop with multilangual 
950        if ('' == 'true') {
951            _containerSelector = 'div.post-container.active'
952        } else {
953            _containerSelector = 'div.post-container'
954        }
955
956        // init
957        var P = $(_containerSelector),a,n,t,l,i,c;
958        a = P.find('h1,h2,h3,h4,h5,h6');
959
960        // clean
961        $(selector).html('')
962
963        // appending
964        a.each(function () {
965            n = $(this).prop('tagName').toLowerCase();
966            i = "#"+$(this).prop('id');
967            t = $(this).text();
968            c = $('<a href="'+i+'" rel="nofollow">'+t+'</a>');
969            l = $('<li class="'+n+'_nav"></li>').append(c);
970            $(selector).append(l);
971        });
972        return true;
973    }
974
975    generateCatalog(".catalog-body");
976
977    // toggle side catalog
978    $(".catalog-toggle").click((function(e){
979        e.preventDefault();
980        $('.side-catalog').toggleClass("fold")
981    }))
982
983    /*
984     * Doc: https://github.com/davist11/jQuery-One-Page-Nav
985     * Fork by Hux to support padding
986     */
987    async("/js/jquery.nav.js", function () {
988        $('.catalog-body').onePageNav({
989            currentClass: "active",
990            changeHash: !1,
991            easing: "swing",
992            filter: "",
993            scrollSpeed: 700,
994            scrollOffset: 0,
995            scrollThreshold: .2,
996            begin: null,
997            end: null,
998            scrollChange: null,
999            padding: 80
1000        });
1001    });
1002</script>
1002
1003
1004
1005
1006<!-- Multi-Lingual -->
1007
1008
1009
1010
1011<!-- Image to hack wechat -->
1012<img src="/img/site/icon.png" width="0" height="0" />
1013<!-- Migrate from head to bottom, no longer block render and still work -->
1014
1015<script type="module" src="https://static.cloudflareinsights.com/beacon.min.js/v31edd6df95cf4e85bb4c19e7a9bdbcba1788362987495" integrity="sha512-iIg7k2xntmwu6/uSb5tpc/hySgZc4eoL31yB29W6tJFo2akwjPWcEqnCEdJvGexCL0KEQwVYv5BlowfhVz26hg==" data-cf-beacon='{"version":"2024.11.0","token":"cc8aae5433c64f15922ee641785c7a8d","r":1,"spa":2}' crossorigin="anonymous"></script>
1015
1016</body>
1017
1018</html>

Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.