-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathhow_to_compare_text.html
1 lines (1 loc) · 17.5 KB
/
how_to_compare_text.html
1
<!doctype html><html lang="zh-CN" class="night"><head><meta charset="utf-8"><meta content="width=device-width,initial-scale=1,maximum-scale=4,user-scalable=0" name="viewport"><title>Ede's Blog</title><meta name="description" content="Try to be a qualified programmer"><meta property="og:type" content="website"><meta property="og:description" content="Try to be a qualified programmer"><meta property="og:title" content="Ede's Blog"><meta property="og:site_name" content="Ede's Blog"><meta property="og:url" content="https://ede.ink"><meta property="og:image" content="https://edeity.oss-cn-shenzhen.aliyuncs.com/public/edeity_o.png"><link rel="shortcut icon" href="/favicon.ico" type="image/x-icon"><link rel="mainfest" href="/mainfest.json"><link rel="stylesheet" href="/public/css/common.css"><link rel="stylesheet" href="//at.alicdn.com/t/font_707055_4b9og9sc5lx.css"><script>!function(){var e=-1!==window.location.search.indexOf("theme=night")||"night"===window.localStorage.getItem("edeity-theme_theme"),t=-1!==window.location.search.indexOf("theme=light")||"light"===window.localStorage.getItem("edeity-theme_theme");(new Date).getHours();var n=document.querySelector("html");e?n.classList.add("night"):t?n.classList.remove("night"):n.classList.add("night")}(),document.addEventListener("DOMContentLoaded",function(){null!==document.querySelector("ol.toc")&&(document.querySelector("#nav-bar").style.cssText="display: block")})</script><script async src="https://www.googletagmanager.com/gtag/js?id=G-M3J9QSEE2Z"></script><script>function gtag(){dataLayer.push(arguments)}window.dataLayer=window.dataLayer||[],gtag("js",new Date),gtag("config","G-M3J9QSEE2Z")</script><meta name="generator" content="Hexo 5.0.0"></head><body><div class="loading"></div><div id="switch" data-switch="{"toc":true,"use_pwa":false}"></div><header class="fullscreen"><div class="toolbar"><i class="iconfont icon-menu"></i></div><h1><a href="/">Ede's Blog</a></h1><div class="head-link"><a class="btn waves" href="/"><span><i class="iconfont icon-home">Home </i></span></a><a class="btn waves" href="/about/index.html"><span><i class="iconfont icon-me">About </i></span></a><a class="btn waves" target="_blank" rel="noopener" href="https://github.com/edeink"><span><i class="iconfont icon-github">Github</i></span></a></div></header><div class="some-link"><a class="btn" id="light-or-not"><i class="iconfont icon-light"></i> </a><a style="display:none" class="btn" id="up-to-top"><i class="iconfont icon-up"></i></a></div><div id="nav-bar" style="display:none"><div class="toc"><ol class="toc"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%89%8D%E7%AB%AF%E5%B0%8F%E9%85%92%E9%A6%86"><span class="toc-number">1.</span> <span class="toc-text">前端小酒馆</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8C%91%E8%A1%85%E7%9A%84%E6%96%87%E5%AD%97"><span class="toc-number">2.</span> <span class="toc-text">挑衅的文字</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%B1%82%E6%8F%B4-Mr-RTED"><span class="toc-number">3.</span> <span class="toc-text">求援 Mr RTED</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%81%B6%E9%81%87-Mr-DP"><span class="toc-number">4.</span> <span class="toc-text">偶遇 Mr DP</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Git%E4%BF%B1%E4%B9%90%E9%83%A8"><span class="toc-number">5.</span> <span class="toc-text">Git俱乐部</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%AE%8C%E6%88%90%E6%8C%91%E6%88%98"><span class="toc-number">6.</span> <span class="toc-text">完成挑战</span></a></li></ol><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%BB%93%E8%AF%AD"><span class="toc-number"></span> <span class="toc-text">结语</span></a></li></div></div><main id="content-main" class="section"><div class="list-item"><h1 class="post-title"><a id="Mr. Myers" class="article-link" href="">Mr. Myers</a></h1><div class="post-meta"><time class="meta published">Sep 15, 2021</time></div><div class="article"><div class="post-excerpt markdown-body"><div class="alert">本文不涉及技术细节，仅心血来潮瞎编故事。<small>（细节请通过外链了解）</small></div><div class="warn">各单位注意，本文有“尴尬兽”出没，老少妇幼请绕路。</div><p>很高兴认识Mr. Myers先生。我们两个本无交集。</p><h3 id="前端小酒馆"><a href="#前端小酒馆" class="headerlink" title="前端小酒馆"></a>前端小酒馆</h3><p>我，偏居一隅的小前端，琐碎于编辑器酒馆的两三事，无非是今天擦擦那平淡无奇的模态框，明天看看哪位需要点燃一支列表，小心翼翼地为他们端去一杯圆角酒，里面放些带阴影的小饼干。大多数的客人都是礼貌：“哦，你做的下拉框好看极了，我很喜欢”。“哇，那是你新种的光标吗，一闪一闪的很可爱”。</p><p>但也会有一些喝醉了的顾客，他们嘴里叫骂着：“放大，再大点，再大点，这个字体再大点，我的眼睛看不清，你这点字体是给狗看的吗”？？！！有时候，我差点忍不住发了脾气，但我说出脏话的一瞬间，我又想起我家那位老人家，岁月已经给她留了太多的痕迹，那些臃肿的代码，已经深深地烙在她的皮肤上，她的每一次刷新，每一次滑动都显得不是那么吃力。早些时候，我为她送上了新的滑动轮椅，是模拟动力的，她高兴极了，在我面前飞快地滑来滑去，像个小孩子一样。看着她轻快的样子，我又感受到我存在的意义。</p><p>“现在光景不好，前端调酒这行越来越难混了，我不能发脾气，我要珍惜现在的工作”。我自言自语，又换上了笑脸：“来，亲爱的上帝，这是你要的<del>飞天螺旋亲*大爆炸的</del>10086px字体”。</p><p><img src="https://edeity.oss-cn-shenzhen.aliyuncs.com/2021/jiuguan.jpeg" alt="酒馆"></p><div class="img-desc">快进来，找个<del>妹子</del>位置随便<del>*</del>坐</div><h3 id="挑衅的文字"><a href="#挑衅的文字" class="headerlink" title="挑衅的文字"></a>挑衅的文字</h3><p>而后，平常的日子发生了一点点的变化。</p><p>那是一个奇妙的上午，我像往常那样在前台调着Css鸡尾酒。突然来了一个恶 <del>Bug</del> 霸，他人很单薄，瘦长的脸像把尖刀插在自己的脖子里，左右手分别提着两个破麻袋。</p><p>他径直向前台走来，拨开面前的酒杯，把麻袋里凌乱的东西分别倒在我的桌上：是文字！！一个个文字，我来不及细看，但很多，堆起来像两座小山，可能有好几万吧。接着，他用阴沉的话暗暗说道：”给你一天的时间，在十二点之前，给我找出不一样的地方，不然？不然我让在场的所有家伙，都保！存！不！了！“。</p><p>他当时低着头，说的话的声音很小，像蚊子一样，甚至有些沙哑，但每一句，我都听清了，就像一把小匕首，虽不显眼，却让你惊出一身冷汗。</p><p>我颤颤巍巍地说：”也许，可以让事务先生来，他特别擅长处理和记录变化，比如，我们是不是可以先记录一个删除，再记录一个新增…“。</p><p>不！”他突然提高了音量，打断了我：“这就是一坨东西，没有前因，我只要后果！！”</p><p>我顿住了，我可从来没有遇到这种情况。没有前因，却要结果。这怎么可能做到。</p><p>我有些紧张：”也许，也许，可以把他们变成树，我认识<a target="_blank" rel="noopener" href="http://vldb.org/pvldb/vol5/p334_mateuszpawlik_vldb2012.pdf">Mr.RTED</a>先生，他，他比较擅长，嗯，怎么说，处理树这种东西。我和他很熟。是的。“我越说越小声，因为事实上，我和Mr.RTED并不熟，我只是从别人的只言片语中了解到他的存在，准确而言，除了名字，我对他一无所知。</p><p>我面前的陌生人不说话，他好像相信了我的话，又好像一点都不信，眼里飘过一些不屑。他一把拉过旁边的高脚椅，坐了上去，说道：“那好，你叫他们过来试试。“</p><h3 id="求援-Mr-RTED"><a href="#求援-Mr-RTED" class="headerlink" title="求援 Mr RTED"></a>求援 Mr RTED</h3><p>我不敢迟疑，赶忙去联系Mr RTED。但他并不好联系，他属于那种，住在城堡里的贵族。我来到他的城堡，摇响门铃。是管家探的头。管家说，他家主人在睡午觉了，或者在研究什么文件啊，基因啊，净是些我没听过的东西，让我在门外等等。</p><p>我在门外等，等啊等，等啊等，天空飘过来一些云多，又飘走了，没人搭理我。不远处的溪水哗啦啦地流，冲刷着石头，冲刷着地面，没人搭理我。微风吹拂，从远方吹来，吹向远方，没人搭理我。不知不觉，我睡着了，我觉得我不懂他们的世界。又不知过了多久，管家叫醒了我，管家说：你走吧，少爷说不合适。</p><p>我伤心极了。不知道如何是好，甚至不想回去。我觉得，酒馆里的那些页面，和我，又有什么关系呢？那些酗酒的人，他们保存不了和我，又有什么关系呢？但，我又想起了我家的那位，她还在等着我，我说要给她换上新的UI衣服，帮她把插件都规划摆放整齐。“不，我不能就这么走了，可是…可是我又能怎么办呢”？</p><h3 id="偶遇-Mr-DP"><a href="#偶遇-Mr-DP" class="headerlink" title="偶遇 Mr DP"></a>偶遇 Mr DP</h3><p>我一脸惆怅地走着，不知走了多久。突然，有人在我耳边说了话：“嘿，乐乐，干嘛一副愁面苦脸的样子，是遇到了什么麻烦吗？也许我可以帮你一把”？</p><p>我抬头，啊，是高中的老同学：“是你，动态规划。我可愁死了！”我一五一十地将事情告诉了他。“你有什么办法吗？”</p><p>动态规划皱了皱眉头：“也许，我可以帮忙，毕竟我干过差不多的事情。对，就是上次，还记得吗，我们在<a target="_blank" rel="noopener" href="https://www.jianshu.com/p/a617d20162cf">编辑距离</a>也解决过差不多的问题！让我试试。”</p><p>我高兴极了，像在汪洋大海中抓住了一块木板。“试试！咋们试试！”</p><p>我分别从两个口袋里掏出了几百字，那是我临走前塞进口袋里的。我们把这些字体摆成了N*N的小矩阵，将问题拆解，求重复的子问题。我们忙活着……</p><p>“成了”！我不敢相信我的眼睛，两者的差异，正整齐地罗列在我们面前，就好像我们正在经历着这些文字的生平。我有点怀疑，又赶忙确认了两遍。</p><p>“没有问题！真的成了！”我们抱在一起，又蹦又跳：“编辑器酒馆的大伙们有救了！”我甚至激动地流出了一点眼泪。我望向天空，啊，广阔的天空，啊，不！我的心情突然从山峰掉到了低谷：“不，不！不能够！”</p><p>动态规划一脸不解：“怎么，我们不是有答案了吗？”我失望地指了指天空：此时的天空已一片黯淡，远处的晚霞也逐渐消去了颜色。“太晚了，现在已经是傍晚了，按照我们的速度，我们只能找出几千字的不同，我们需要<code>O(n^2)</code>的时间，他，他，不会等我们这么久的。”</p><p>动态规划貌似也意识到了这点。“啊，是啊，毕竟酒馆里的文字可是有几万字。”</p><p>于是，我们又变得垂头丧气，瘫坐在石头上。</p><p>沉默了些许，周围一片死寂。我想说些什么，但又什么都说不出来。“也许我，以前好好学习一下算法，就好了。你知道吗？去年我买了本《算法导论》，已经看了十几章了…但，后来我搬家了，我懒，我没时间看….”。</p><p>”哎，我知道，自你从上大学起，就喜欢折腾那些看得见的，什么应用啊，界面啊，而那些逻辑复杂的，真正的本领，你却大大咧咧，没有耐心细看“。</p><p>我苦笑着，但突然又想起什么：”啊，应用，你说应用，我突然想起一个应用俱乐部，它很出名，里面的人也许会有办法！“</p><p>”什么俱乐部“？</p><p>”Git“！</p><p>”Git“？</p><p>”对，我曾在那见过一些魔法！那时我还小！哦，天哪！我觉得可以！“</p><h3 id="Git俱乐部"><a href="#Git俱乐部" class="headerlink" title="Git俱乐部"></a>Git俱乐部</h3><p>Git俱乐部离我们很近，也很好辨认，那里的人从来不少，来自全国各地的编程者们，都喜欢来这里锻炼，交谈业界内新鲜的事情。一个大大的“G”字，发着黄色的淡光，嵌在牌匾上，而牌匾，则挂在一楼和二楼之间。</p><p>我们很快就达了那里，推开半掩的门，里面还像往常那样热闹。”Pull！Push！用力！Pull！Push！加油！“有一群人在有节奏地举着杠铃，相互鼓舞。</p><p>”你看看他们，Gay里Gay气的。“动态规划打趣到，我狠狠地瞪了他一眼，示意他不要说些不合时宜的话。</p><p>俱乐部的尽头，有个小房间，尽管房号已蒙上一些灰尘，门把手却非常崭新，证明常有人来往。门号上如是写着：”DIFF“。</p><p>我小心翼翼推门进去，里面是一间办公室，几张桌椅。”您好，请问，请问是Diff办事处吗“？</p><p>正门的先生抬头看了下我们：”哦？看看，我们好久没有看到你这样的年轻小伙子了，现在他们都喜欢请代理商，像sourcetree、gitlab这种，请问有什么事情吗？“</p><p>”我，我，遇到了一些麻烦，有人在我们的酒馆闹事，他在我们酒馆洒了两堆文字，很多“。我顿了顿：”大概有好几万，也许要十几万，他让我们把这些拾起来，分别找…找出不同，在十二点之前！“。”我们尝试了很多办法，我们也做了一些，成绩，对，我们分了几百字”。我看了看动态规划，“但是剩下的时间不够了，也许时间再多一点就好了，所以我们觉得，也许您可以…“。</p><p>那位先生哈哈大笑起来：”看来你走运了，我刚好擅长处理文本的不同。“他站了起来，整理整理衣服上的褶皱，”容我自我介绍一下，我叫Myers，你们可以叫我<a target="_blank" rel="noopener" href="http://www.grantjenks.com/wiki/_media/ideas:simple_fast_algorithms_for_the_editing_distance_between_tree_and_related_problems.pdf">Mr.Myers</a>“。</p><p>我眼睛里又重新燃起了希望：”真的吗，真的可以更快吗”？</p><p>”可以，也许快得不是很多，但应该足够了。”Myers先生看了看手上的表：“你瞧，<strong>算法的魅力，大多数应用场合，就是根据各种上下文，把N变成Log(n)。</strong>而我，刚好可以。我只需要<code>O(Nlog(n))</code>的时间，准确来说，是<code>O(Nlog(m+n))</code>。来，我陪你们走一趟“。</p><p>“真的吗？怎么做到的”？</p><p>“哦，因为我更‘贪心’，哈哈哈，我们边走边聊“。语毕，Mr.Myers便披上了外套，从抽屉里拿出了一个<a target="_blank" rel="noopener" href="https://github.com/google/diff-match-patch">盒子</a>：“瞧，这是我的一位Google朋友为我量身定做的！”</p><h3 id="完成挑战"><a href="#完成挑战" class="headerlink" title="完成挑战"></a>完成挑战</h3><p>我们陪同myers先生回到了编辑器酒馆，恶霸还在那里，神态越发嚣张。“怎么，还没有我要的答案吗？没有的话，我就…”。</p><p>没等恶霸说完，Myers先生便前行一步，打开盒子。桌面上凌乱的文字突然像有了生命，像蛇一样，钻进盒子里。不一会儿，又从盒子里爬了出来，整齐地摆在两边。不同的是，他们身上有些地方，都被标上了颜色。</p><p>“是差异！我们成功了！”不知是谁喊了一声，酒馆里顿时一阵欢呼，紧张的气氛荡然无存。一切来得那么突然，转瞬之间。</p><p>那位恶霸兴许还想说些什么，但Myers先生抢先发问：“那么，你还有什么事情吗”？Myers先生的声音很宏厚，充满了自信。</p><p>恶霸知道，哪怕他拿出更多的字体，兴许几十万，Myers也会用那神奇的小盒子，把他收拾得服服帖帖。唯有恶狠狠地说：“你等着，我还会回来的”！便灰溜溜地走出了酒馆。</p><h2 id="结语"><a href="#结语" class="headerlink" title="结语"></a>结语</h2><p>“这就是我和Myers先生相识的故事”。我如是回忆到。</p><p>对面的小伙子听完，感叹道：“真的太神奇了，多炫酷的魔法”。</p><p>我微笑着：“Myers先生说，<strong>只有不认真学习的人，才觉得世间充满了魔法。</strong>”。</p><p>你看，这就是魔法的<a target="_blank" rel="noopener" href="https://cjting.me/2017/05/13/how-git-generate-diff/">奥秘</a>。</p></div></div></div><div class="more section"><div class="pre"><a class="article-link" href="/typo.html"><i class="iconfont icon-right"></i> <span>我所了解的编辑器</span></a></div><div class="next"><a class="article-link" href="/qinghai travel.html">苦行青海 <i class="iconfont icon-right"></i></a></div></div></main></body><footer class="section fullscreen"><div class="footer-desc">Edeink © 2015-2022 · Powered by Hexo</div></footer><script src="https://cdn.bootcdn.net/ajax/libs/jquery/3.6.0/jquery.js"></script><script src="/public/js/init.js"></script></html>