https://segmentfault.com/a/1190000006025876
设计题的三个要点:
1.组件分解
2.并行计算
3.利用缓存
https://rao.gitbooks.io/first-system-design/content/
DSR模式:
那么我们又想使用LB的功能,同时又不愿意有这样的性能下降,这时怎么办?性能的下降是由于所有的数据包都要经过LB设备。那么我们能不能让数据包不经过LB设备呢?这时,就需要让SLB另外一种应用拓扑Direct Server Reply,即DSR模式。顾名思义,DSR模式下,server的response包不会经过LB,直接发往client。而所有的client发送的request数据包,仍然经过LB设备。
使用DSR模式,看上去只有server的response不经过LB设备,只有单边的流量得到了优化。但是在一般的CS应用中,client的request往往比较简单,数据较小较少,而server的response的数据较多较大。一般server response的流量可以占到总流量的80%到90%时,使用DSR模式,可以有效的提高性能,又不损失SLB的灵活性。
https://idf-shadow.gitbooks.io/sytem-design-hanbook/content/high_level_concepts.html
http://itsumomono.blogspot.com/2015/08/compare-filedata-bulk-similarity.html
1. Check same: Checksum functions are related to hash functions, fingerprints, randomization functions, and cryptographic hash functions.
2. Scoring similarity:
Jaccard similarity
w-shingling
minHash
LSH(locality sensitive hashing)
https://en.wikipedia.org/wiki/Locality-sensitive_hashing
https://en.wikipedia.org/wiki/W-shingling
k-gram/k-mer
(a,rose,is,a,rose,is,a,rose)
in information retrieval and text mining, each term is notionally assigned a different dimension and a document is characterised by a vector where the value of each dimension corresponds to the number of times that term appears in the document. Cosine similarity then gives a useful measure of how similar two documents are likely to be in terms of their subject matter.[
http://itsumomono.blogspot.com/2015/07/rest-post-vs-put.html
在HTTP中,PUT被定义为indempotent的方法,POST则不是,这是一个很重要的区别。
“Methods can also have the property of "idempotence" in that (aside from error or expiration issues) the side-effects of N > 0 identical requests is the same as for a single request.”
上面的话就是说,如果一个方法重复执行多次,产生的效果是一样的,那就是idempotent的。
举一个简单的例子,假如有一个博客系统提供一个Web API,模式是这样http://superblogging/blogs/post/{blog-name},很简单,将{blog-name}替换为我们的blog名字,往这个URI发送一个HTTP PUT或者POST请求,HTTP的body部分就是博文,这是一个很简单的REST API例子。我们应该用PUT方法还是POST方法?取决于这个REST服务的行为是否是idempotent的,假如我们发送两个http://superblogging/blogs/post/Sample请求,服务器端是什么样的行为?如果产生了两个博客帖子,那就说明这个服务不是idempotent的,因为多次使用产生了副作用了嘛;如果后一个请求把第一个请求覆盖掉了,那这个服务就是idempotent的。前一种情况,应该使用POST方法,后一种情况,应该使用PUT方法。
设计题的三个要点:
1.组件分解
2.并行计算
3.利用缓存
1. Spell Checker
场景:
给一个word,假设这是一个拼错的英文单词,我们应返回一个list of word,list里的words都是word可能的正确拼写。
分析:
有两个概念要clarify:
1.对于“拼错"这个概念,什么叫"拼错",什么叫"拼对",都是相对的,我们可以假设一本词典,这里面所有的单词都是拼对的,其他的都是拼错的。还有一个延伸就是,如果这个词”拼对“了,程序还check不check呢?
2.给一个word,我们先生成一堆和他很像的词,这些词可能拼对也可能拼错,我们把拼对的返回,问题在于,这里的”像“怎么界定?这里我们假设 - “像”,表示所有和word的edit distance(Levenshtein distance) exactly为2的单词们。
1.对于“拼错"这个概念,什么叫"拼错",什么叫"拼对",都是相对的,我们可以假设一本词典,这里面所有的单词都是拼对的,其他的都是拼错的。还有一个延伸就是,如果这个词”拼对“了,程序还check不check呢?
2.给一个word,我们先生成一堆和他很像的词,这些词可能拼对也可能拼错,我们把拼对的返回,问题在于,这里的”像“怎么界定?这里我们假设 - “像”,表示所有和word的edit distance(Levenshtein distance) exactly为2的单词们。
数据结构:
把词典预处理成一个map,key是所有的字典单词,value无所谓。我们只想快速的知道这个word是不是词典(拼对)的,对这个单词的其他性质并不关心。
核心算法:
给一个word,生成所有与这个word的edit distance(只substitute,不add也不remove)为2的所有string来,挨个去查hashmap。查出来的这些按照某种rank algorithm排序选出最高的10条。
至于这个排序算法,请看本题的后续部分。
至于这个排序算法,请看本题的后续部分。
复杂度:
对于一个request_spell_check(String word), 假设字母有m(英语的话就是26)个,单词长n(一般来讲1~15)
时间O(m^2 * n^2),因为设定edit distance为2,改装一个word的可能性有n(n-1)(m-1)^2/2种,假设改写一种是一条java语句(一次循环),那么改写一个interesting(长度为11)大约需要循环次数为:34375,假设1s内一台电脑可以运行10^8条java语句,那么每个request的耗时大约是0.3ms,1ms这个级别,是可以接受的。
空间O(1),通过上面的查找,查找的结果可能会非常大,我们只要返回一个ranked list of suggestions就好了,比如rank最高的十条。
时间O(m^2 * n^2),因为设定edit distance为2,改装一个word的可能性有n(n-1)(m-1)^2/2种,假设改写一种是一条java语句(一次循环),那么改写一个interesting(长度为11)大约需要循环次数为:34375,假设1s内一台电脑可以运行10^8条java语句,那么每个request的耗时大约是0.3ms,1ms这个级别,是可以接受的。
空间O(1),通过上面的查找,查找的结果可能会非常大,我们只要返回一个ranked list of suggestions就好了,比如rank最高的十条。
后续:
关于排序算法,输入是一个list of word,这些word都在词典里,是拼对的词,现在要从里面找出10条最可能是答案的词,明显是一个没有标准答案的问题,所以要根据情况分析trade-off:
- Typing errors model,我们的排序就要根据键盘的layout来判断了;
- Phonetic modeling,情景:我想打一个词,只会读,不会写,比如kat打出了cat。解决方法是,把输入的单词按phonemes划分,每段按发音进行替换。
- History of refinements,搜集用户打错的数据 - 用户经常会打一个词,然后删了,打了另一个词,然后request请求,这两个词第一个词就是潜在的错误拼写,第二个是正确拼写。
- Stemming,通过把["computers", "computer", "compute", "computing"]提取为"compute",当我们拿到一个word时,对他stemming,然后把stemming结果的列表返回。
2. Stemming Problem
场景:
Stemming是搜索引擎normalize环节的一个技术,中文叫做词干提取,顾名思义,即把["computers", "computer", "compute", "computing"]提取为"compute"。Stemming既用在query string上,也用在document的存储中。前者可以延伸语义,比如查compute的时候很可能对computer感兴趣或者你想查的根本就是computer。后者可以大大降低搜索引擎索引的存储大小,也可以提高搜索效率。
分析:
Stemming明显是一个没有标准答案的问题,基本上是在trade-off,根据情景解决问题。而且这个题目太大,这里只是简述。
本质上Stemming就是根据某种规则(rule)重写(rewrite)。
本质上Stemming就是根据某种规则(rule)重写(rewrite)。
- 重写,基本都是focus在后缀(suffix)上,改后缀(wolves -> wolf),删后缀(cars -> car)。
- 规则,这些规则干的事儿就是,先找到哪儿到哪儿是后缀(应该有个后缀表什么的),然后把这个后缀transform一下(应该也有个转换表什么的)。
一个有效的实现方法是根据这些规则建立一个Finite State Machine - 有限状态机。
后续:
越sophisticated的system会有更多的exceptions,即考虑更多地特殊情况,比如Chinese -> China这种。
Porter stemmer,作者Martin Porter,目前是公认最好的英语stemming algorithm。
其他的方法有:stochastic methods, n-gram based approaches.
Porter stemmer,作者Martin Porter,目前是公认最好的英语stemming algorithm。
其他的方法有:stochastic methods, n-gram based approaches.
3. Plagiarism Detector
场景:
在一堆文章里找相似的文章对们。
这里文章我们看做String,两篇文章如果有长度为k的公共substring,就说他们是相似的。
这里文章我们看做String,两篇文章如果有长度为k的公共substring,就说他们是相似的。
分析:
对某个String(文章),假设这个String长度为len,那么对这个String计算len-k+1个hashcode。
举例比如:"abcdefg"这篇文章,取k=3,我们对"abc","bcd","cde","def","efg"这5个substring分别做5次hash,存到一个大大的HashTable里,key为hash的值,value为文章id以及offset。
这样当遇到collision(这里不是指发生了多对一映射,假设hashfunction很好可以一对一映射)的时候,我们就知道那两篇文章是相似的。
这里就需要一个可以incrementally更新的hash算法,这种hash方法叫rolling hash,可参见Rabin-Karp算法,Leetcode这道题 - 187. Repeated DNA Sequences。
举例比如:"abcdefg"这篇文章,取k=3,我们对"abc","bcd","cde","def","efg"这5个substring分别做5次hash,存到一个大大的HashTable里,key为hash的值,value为文章id以及offset。
这样当遇到collision(这里不是指发生了多对一映射,假设hashfunction很好可以一对一映射)的时候,我们就知道那两篇文章是相似的。
这里就需要一个可以incrementally更新的hash算法,这种hash方法叫rolling hash,可参见Rabin-Karp算法,Leetcode这道题 - 187. Repeated DNA Sequences。
这里说一下为什么hash算法取模的size都是质数:
好的HASH函数需要把原始数据均匀地分布到HASH数组里原始数据不大会是真正的随机的,可能有某些规律,比如大部分是偶数,这时候如果HASH数组容量是偶数,容易使原始数据HASH后不会均匀分布。 比如 2 4 6 8 10 12这6个数,如果对
6 取余 得到 2 4 0 2 4 0 只会得到3种HASH值,冲突会很多 如果对 7 取余 得到 2 4 6 1 3 5
得到6种HASH值,没有冲突同样地,如果数据都是3的倍数,而HASH数组容量是3的倍数,HASH后也容易有冲突 用一个质数则会减少冲突的概率
这个HashTable的size要非常大,这样不同substring映射到同一个hashcode的几率会小。
如果想要省空间,且对结果的精确度要求不高,可以不存所有的substring的hashcode,而只是存特定的hashcode,比如最后5个bit都是0的hashcode,这样我们只存所有substring的1/(2^5)即可。
上面的方法存在很多false positive,比如假设这里文章指的是html页面,所有的文章几乎在开头都会调用同样的javascript段,我们的方法就会认为这些html都是相似的。这里我们就需要在判断前,对这些文章进行预处理,把headers去掉。
上述的方法在每篇文章(String)都很长,且这些文章分布在很多servers的时候,尤其好用。mapreduce就很适合干这个事。
如果想要省空间,且对结果的精确度要求不高,可以不存所有的substring的hashcode,而只是存特定的hashcode,比如最后5个bit都是0的hashcode,这样我们只存所有substring的1/(2^5)即可。
上面的方法存在很多false positive,比如假设这里文章指的是html页面,所有的文章几乎在开头都会调用同样的javascript段,我们的方法就会认为这些html都是相似的。这里我们就需要在判断前,对这些文章进行预处理,把headers去掉。
上述的方法在每篇文章(String)都很长,且这些文章分布在很多servers的时候,尤其好用。mapreduce就很适合干这个事。
4. Pair Users By Attributes
场景:
在social network里,每个用户(user)有一些属性(attributes),现在我们要把属性相同的用户配对。
分析:
用户怎么表示:用户id - 32位的int
属性怎么表示:strings
怎么叫配对:每次读入一个user(有他的id和属性们),从之前未成功配对的集合里找有相同属性们的用户。
属性怎么表示:strings
怎么叫配对:每次读入一个user(有他的id和属性们),从之前未成功配对的集合里找有相同属性们的用户。
数据结构:
map。
算法:
第一个层面:brute force。
假设连续读入n个用户,对于每个读入的用户,与unpaired set里每个用户进行attributes的比对,时间复杂度为O(N^2).
第二个层面:hashtable,key存attributes组合,value存用户。
问题是怎么把一堆attributes的组合变成一个key,即这个hashfunction怎么搞?
如果属性很少,只有几个,比如只有"蓝色","绿色","红色","吉他","钢琴","提亲","爵士鼓",那完全可以用一个bit array一波带走,然后把这个bit array随便hash一下。
时间复杂度O(nm),n为用户数,m是所有distinct attribute数,对于上面的例子就是7。时间消耗就是把每个用户的attributes转化成bit array然后把bit array哈希的时间。
第三个层面:如果attribute有很多,有1亿个,且大部分的用户只有很少的几条attributes,这样上面的方法就不好用了,对于每一个用户都要看这一亿个attribute里有没有,是浪费时间的。
在这么一个sparse subsets里,更好的方法是,直接把这些attribute们concatenate成一个string,当然concatenation之前先排个序,然后对这个string使用hash function。
时间复杂度是O(NM),n是用户数,m是平均每个用户的attributes concatenation之后的长度。
假设连续读入n个用户,对于每个读入的用户,与unpaired set里每个用户进行attributes的比对,时间复杂度为O(N^2).
第二个层面:hashtable,key存attributes组合,value存用户。
问题是怎么把一堆attributes的组合变成一个key,即这个hashfunction怎么搞?
如果属性很少,只有几个,比如只有"蓝色","绿色","红色","吉他","钢琴","提亲","爵士鼓",那完全可以用一个bit array一波带走,然后把这个bit array随便hash一下。
时间复杂度O(nm),n为用户数,m是所有distinct attribute数,对于上面的例子就是7。时间消耗就是把每个用户的attributes转化成bit array然后把bit array哈希的时间。
第三个层面:如果attribute有很多,有1亿个,且大部分的用户只有很少的几条attributes,这样上面的方法就不好用了,对于每一个用户都要看这一亿个attribute里有没有,是浪费时间的。
在这么一个sparse subsets里,更好的方法是,直接把这些attribute们concatenate成一个string,当然concatenation之前先排个序,然后对这个string使用hash function。
时间复杂度是O(NM),n是用户数,m是平均每个用户的attributes concatenation之后的长度。
5. Detect Video Copyright Infringement
场景:
故事是这样的:有一天华谊发现youku.com上有人上传了”让子弹飞高清蓝光“整部电影,这侵犯了华谊的版权,假设你是华谊的工程师,如何给定华谊的视频库,判断youku.com哪些视频是侵权的。
分析:
和第3题要干的事儿一样,但是把document换成了video。同理也可以换成audio,这里讨论video。
判断对象是video的话,就不能像document那么干了(rolling hash),原因在于即使内容相同(比如都是“让子弹飞”),但不同的视频可以压缩成不同的格式(flv,mp4,avi),有不同的分辨率(1366x768, 1024×768),不同的压缩程度。
判断对象是video的话,就不能像document那么干了(rolling hash),原因在于即使内容相同(比如都是“让子弹飞”),但不同的视频可以压缩成不同的格式(flv,mp4,avi),有不同的分辨率(1366x768, 1024×768),不同的压缩程度。
算法:
把所有视频都转换成相同的格式(format),分辨率(resolution)和压缩度(level of compression)。注意,这么做了之后,相同内容的视频仍然不是相同的文件。但是,经过了这样的normalization之后,我们就可以开始对每个视频生成signature了。
- 最简单的signature生成方法:对每一帧(frame)用一个bit根据一个亮度(brightness)阈值赋0或1,这个阈值是average的brightness。
- 更好的signature生成方法:对每帧用三个bit表示R,G,B,每个bit的取值根据R,G,B的intensity阈值赋0或1。
- 再精确一点的signature生成方法:把每一帧分成几个region,每个region求出一个R,G,B的3个bit,再把这些region contatenate起来。
后续:
以上算法是algorithmic的,还有其他的手法:
让用户来标明是否侵权(有报酬的);和以前确认了的侵权视频进行比对,看是否完全一样;看视频header的meta-information,等等。
让用户来标明是否侵权(有报酬的);和以前确认了的侵权视频进行比对,看是否完全一样;看视频header的meta-information,等等。
6. Design TeX
场景:
TeX是一个排版系统,写论文,出版社全用它。好处是不依赖平台,输出是设备无关的。像JVM一样。妈妈再也不用担心Windows下编辑的书稿在Mac里凌乱了。
一旦TeX处理了你的文件,你所得到的 DVI 文件就可以被送到任何输出设备如打印机,屏幕等并且总会得到相同的结果,而这与这些输出设备的限制没有任何关系。这说明 DVI 文件中所有的元素,从页面设置到文本中字符的位置都被固定,不能更改。TeX是一个非常多才多艺的程序。它不但可以编辑论文,书籍,幻灯片,学术杂志,个人简历,还可以 编辑乐谱,化学分子图,电路图,国际象棋,中国象棋,甚至围棋棋谱,……事实上只有少量文档不适合用TeX编辑。
问,怎么设计TeX?
一旦TeX处理了你的文件,你所得到的 DVI 文件就可以被送到任何输出设备如打印机,屏幕等并且总会得到相同的结果,而这与这些输出设备的限制没有任何关系。这说明 DVI 文件中所有的元素,从页面设置到文本中字符的位置都被固定,不能更改。TeX是一个非常多才多艺的程序。它不但可以编辑论文,书籍,幻灯片,学术杂志,个人简历,还可以 编辑乐谱,化学分子图,电路图,国际象棋,中国象棋,甚至围棋棋谱,……事实上只有少量文档不适合用TeX编辑。
问,怎么设计TeX?
分析:
两方面:
- building blocks,即基本元素,包括字体(fonts)和符号(symbols)怎么存,怎么表示?
- 每个基本元素(symbol和font)最简单的表示方法是用2D array,俗称bit-mapped representation.这样做的问题是,对于resolution要求比较高的设备,这样的空间消耗极大,且不说对一个font来说有不同大小,斜体,粗体之分,这都要另存一份。
- 更好的方法是,我们可以用数学方程来定义symbols。这样我们反而可以更精细地编程生成symbol和font,甚至可以控制字体长宽比(aspect ratio),笔画粗细(stroke width),字体的倾斜度(font slant),描边粒度(serif size)。
- hierarchical layout,布局,即怎么把基本元素漂亮的摆放在一起
- 我们可以把元素(component)抽象成一个矩形的box,所有的都是矩形box,矩形box组装起来成为新的矩形Box.
举例比如:每个symbol是个box(比如@,3,A,d,-,#),line(比如:---)和paragraph都是由box组成的,section title, tables, table entries 以及 images也都是由矩形Box组成的。至于把这些box漂亮地组装起来就用到很多的算法。
后续:
其他的问题还有:enabling cross-referencing, automatically creating indices, supporting colors, and outputting PDF.
7. Design a Search Engine
场景:
给100万个documents,每个平均10KB。输入set of words,返回set of documents,其中每个document都包含这个set of words。假设所有documents可以存放在一台电脑的RAM中。
分析:
不多说,inverted indices走起。
对于每个索引(inverted index),相当于map的一个entry,key是word,value是sorted list of ['document_ID',offset],这里list是先按document_ID,后按offset排序的。
在搜索的时候,比如搜索"beatles nirvana eminem",会分别对三个words找他们的sorted list(为了方便,下面只显示document_ID):
找到了三个词对应的索引条目:
beatles: [1]->[3]->[120]->[789]->[1022]->[7881]->[9912]
nirvana: [1]->[2]->[3]->[456]
grammy : [2]->[3]->[120]
答案就是这三个list的交集,即[3]这个document,求交集的时间复杂度和三个list的长度总和成比例(proportional to the aggregate len of the sequences)。
当然我们可以做一些优化:
对于每个索引(inverted index),相当于map的一个entry,key是word,value是sorted list of ['document_ID',offset],这里list是先按document_ID,后按offset排序的。
在搜索的时候,比如搜索"beatles nirvana eminem",会分别对三个words找他们的sorted list(为了方便,下面只显示document_ID):
找到了三个词对应的索引条目:
beatles: [1]->[3]->[120]->[789]->[1022]->[7881]->[9912]
nirvana: [1]->[2]->[3]->[456]
grammy : [2]->[3]->[120]
答案就是这三个list的交集,即[3]这个document,求交集的时间复杂度和三个list的长度总和成比例(proportional to the aggregate len of the sequences)。
当然我们可以做一些优化:
- Compression:既省空间又提高cache命中率。因为list都是排序了的,可以用增量编码法(delta compression),每个documentId可以省几个bit。
增量编码又叫差分编码,简单地说:不存「2, 4, 6, 9, 7」,而是存「2, 2, 2, 3, -2」。单独使用用处不大,但是在序列式数值常出现时可以帮助压缩大小。 - Cacheing:查询语句(query)一般都是有热点的,因此可以把频率高的query答案cache起来。
- Frequency-based optimization:并不是List的每一个document都返回,只返回top ten就好了。所以我们可以维护两套inverted indices,一套是top ten的,常驻RAM;另一套是剩下的,常驻硬盘。只要大部分的query都访问top ten,那整个系统的throughput 和 latency都是可以接受的。
- Intersection order:合并的顺序对速度有很大影响,要先合并小集合。上面的例子,应先合并nirvana和grammy,然后拿合并的结果与beatles去合并,这样速度最快。
我们也可以用多级索引(multilevel index)增加准确率。对于一个高优先级的web page,可以先将其分解成paragraphs和sentences,然后把这些paragraphs和sentences拿去建索引。
这样的好处是,我们有可能在一个paragraph或者一个sentence里找到query里所有的词,这是分级之前做不到的,之前我们的粒度只能返回文档(web page),现在可以返回paragraph和sentence,精度提高。
这样的好处是,我们有可能在一个paragraph或者一个sentence里找到query里所有的词,这是分级之前做不到的,之前我们的粒度只能返回文档(web page),现在可以返回paragraph和sentence,精度提高。
算法:
这里涉及两个算法题:
- 找两个sorted list的共同元素(intersection):两个指针从头比,一大一小不要小(advance小的pointer),两个相等就添加到result,O(N+M)。
- find the smallest subarray covering all values(搜索的结果里会给一段话,里面highlight出这两个关键字):两个指针维护窗口,O(N)
8. Implement PageRank
场景:
设计一个可以快速计算100亿网页pagerank的系统。
分析:
PageRank的介绍:Introduction to PageRank
简单地说就是一个N(网页数)维矩阵A,其中i行j列的值表示用户从页面j转到页面i的概率。
每个网页作为一个vertex,有超链接的两个网页有一条边,整张图是一个稀疏图,最好用邻接表(adjacency list)来表示。
建表的过程一般是:下载网页(pages),提取网页的超链接。URL由于长度变化很大,所以一般将其hash。
整个算法最耗时的地方在于矩阵乘法的迭代。
邻接表用一台电脑的RAM是放不下的,我们一般有两种做法:
简单地说就是一个N(网页数)维矩阵A,其中i行j列的值表示用户从页面j转到页面i的概率。
每个网页作为一个vertex,有超链接的两个网页有一条边,整张图是一个稀疏图,最好用邻接表(adjacency list)来表示。
建表的过程一般是:下载网页(pages),提取网页的超链接。URL由于长度变化很大,所以一般将其hash。
整个算法最耗时的地方在于矩阵乘法的迭代。
邻接表用一台电脑的RAM是放不下的,我们一般有两种做法:
- Disk-based sorting:
DSR模式:
那么我们又想使用LB的功能,同时又不愿意有这样的性能下降,这时怎么办?性能的下降是由于所有的数据包都要经过LB设备。那么我们能不能让数据包不经过LB设备呢?这时,就需要让SLB另外一种应用拓扑Direct Server Reply,即DSR模式。顾名思义,DSR模式下,server的response包不会经过LB,直接发往client。而所有的client发送的request数据包,仍然经过LB设备。
使用DSR模式,看上去只有server的response不经过LB设备,只有单边的流量得到了优化。但是在一般的CS应用中,client的request往往比较简单,数据较小较少,而server的response的数据较多较大。一般server response的流量可以占到总流量的80%到90%时,使用DSR模式,可以有效的提高性能,又不损失SLB的灵活性。
def: Load Balancer (LB) - distributed requests among servers. Load balancer has the public IP addr, servers IPs (private) not exposed.
Asynchronism Queuing everything
- Key-value: Redis etc.
- Document: MongoDB etc.
- Column: Cassandra etc.
- Graph: Neo4J etc.
http://itsumomono.blogspot.com/2015/08/compare-filedata-bulk-similarity.html
1. Check same: Checksum functions are related to hash functions, fingerprints, randomization functions, and cryptographic hash functions.
2. Scoring similarity:
Jaccard similarity
w-shingling
minHash
LSH(locality sensitive hashing)
https://en.wikipedia.org/wiki/Locality-sensitive_hashing
https://en.wikipedia.org/wiki/W-shingling
k-gram/k-mer
(a,rose,is,a,rose,is,a,rose)
The set of all contiguous sequences of 4 tokens (4-grams) is
- { (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is), (a,rose,is,a), (rose,is,a,rose) } = { (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is) }
in information retrieval and text mining, each term is notionally assigned a different dimension and a document is characterised by a vector where the value of each dimension corresponds to the number of times that term appears in the document. Cosine similarity then gives a useful measure of how similar two documents are likely to be in terms of their subject matter.[
http://itsumomono.blogspot.com/2015/07/rest-post-vs-put.html
本示例介绍在Android平台下通过HTTP协议实现断点续传下载。
我们编写的是Andorid的HTTP协议多线程断点下载应用程序。直接使用单线程下载HTTP文件对我们来说是一件非常简单的事。那么,多线程断点需要什么功能?
1.多线程下载,
2.支持断点。
使用多线程的好处:使用多线程下载会提升文件下载的速度。那么多线程下载文件的过程是:
(1)首先获得下载文件的长度,然后设置本地文件的长度。
HttpURLConnection.getContentLength();//获取下载文件的长度
RandomAccessFile file = new RandomAccessFile("QQWubiSetup.exe","rwd");
file.setLength(filesize);//设置本地文件的长度
(2)根据文件长度和线程数计算每条线程下载的数据长度和下载位置。
如:文件的长度为6M,线程数为3,那么,每条线程下载的数据长度为2M,每条线程开始下载的位置如下图所示。
例如10M大小,使用3个线程来下载,
线程下载的数据长度 (10%3 == 0 ? 10/3:10/3+1) ,第1,2个线程下载长度是4M,第三个线程下载长度为2M
下载开始位置:线程id*每条线程下载的数据长度 = ?
下载结束位置:(线程id+1)*每条线程下载的数据长度-1=?
(3)使用Http的Range头字段指定每条线程从文件的什么位置开始下载,下载到什么位置为止,
如:指定从文件的2M位置开始下载,下载到位置(4M-1byte)为止
代码如下:HttpURLConnection.setRequestProperty("Range", "bytes=2097152-4194303");
(4)保存文件,使用RandomAccessFile类指定每条线程从本地文件的什么位置开始写入数据。
RandomAccessFile threadfile = new RandomAccessFile("QQWubiSetup.exe ","rwd");
threadfile.seek(2097152);//从文件的什么位置开始写入数据
在HTTP中,PUT被定义为indempotent的方法,POST则不是,这是一个很重要的区别。
“Methods can also have the property of "idempotence" in that (aside from error or expiration issues) the side-effects of N > 0 identical requests is the same as for a single request.”
上面的话就是说,如果一个方法重复执行多次,产生的效果是一样的,那就是idempotent的。
举一个简单的例子,假如有一个博客系统提供一个Web API,模式是这样http://superblogging/blogs/post/{blog-name},很简单,将{blog-name}替换为我们的blog名字,往这个URI发送一个HTTP PUT或者POST请求,HTTP的body部分就是博文,这是一个很简单的REST API例子。我们应该用PUT方法还是POST方法?取决于这个REST服务的行为是否是idempotent的,假如我们发送两个http://superblogging/blogs/post/Sample请求,服务器端是什么样的行为?如果产生了两个博客帖子,那就说明这个服务不是idempotent的,因为多次使用产生了副作用了嘛;如果后一个请求把第一个请求覆盖掉了,那这个服务就是idempotent的。前一种情况,应该使用POST方法,后一种情况,应该使用PUT方法。
也许你会觉得这个两个方法的差别没什么大不了的,用错了也不会有什么问题,但是你的服务一放到internet上,如果不遵从HTTP协议的规范,就可能给自己带来麻烦。比如,没准Google Crawler也会访问你的服务,如果让一个不是indempotent的服务可以用indempotent的方法访问,那么你服务器的状态可能就会被Crawler修改,这是不应该发生的。