Skip to main content

btree

· One min read

tree​

A free tree T is an undirected graph that is connected and acyclic.

树有三个属性：

  • 无向
  • 连通
  • 无环

定义​

一共有两个参数: k 和h

性质​

1 每个叶子节点的高度都一样 2.1 除了叶子节点和根节点,其他节点至少有k+1个子节点 2.2 根节点是叶节点或者根节点至少有两个子节点. 3 每个节点最多有2k+1个子节点

核心性质​

v ∈ Parent(p)   有
   <a+1

插入​

插入方式有几种: 1 插入到第一个大于他的节点的同一个页 2 和大于他的最小节点同一个页

删除​

查询​

mvcc

· One min read

mvcc论文 http://www.cs.cmu.edu/~pavlo/papers/p781-wu.pdf

zhihu相关内容: https://zhuanlan.zhihu.com/p/45734268

mvcc是什么?​

mvcc是多版本并发控制

数学基础:​

  • 偏序 (part order ) : 偏序则部分元素可以互相比较
  • 全序 (full order ) : 全序描述的是每个元素都可以比较

complete mutipversion history​

complete mv history 满足下面性质:

  • $ H = h( \cup ^n_{i=0}T_i) for \quad some \quad translation \quad function \quad h $
  • for each $T_i$ and all operations $p_i$ $q_i$ in $T_i$ if $p_i <_i q_i$, then $h(p_i) < h(q_i)$

相关阅读​

数理逻辑

· One min read

数理逻辑我是没有学过的,但是感觉很像编译原理的前端

todolist

· One min read

1 编译原理ssa 2 tensorflow 3 vue原理 4 nlp parser 5 es的search

2020-11-17 我感觉好像什么东西都离不开编译原理,数理逻辑,是我的错觉吗?

parser

· One min read

最大生成树​

初始化: 放入一个node

循环不变量: 是整颗最大生成树的子集

将最大权的放入节点,更新最大权

为什么work​

如果放入的该节点不是最大的生成树的子节点,那么加起来权是最小的

mlp​

训练​

感知机

· One min read

感知机是一个输出是+1 和-1两个值的分类器

多层感知机 输入: 上一层的输出 处理: 感知函数 输出: 经过感知函数处理的值

循环不变式loop invariants

· 2 min read

控制流图​

入口和出口​

入口 --->   判断 ---> 出口
        |    |
        |    |
        |____|

对于每个判断,有两个入口: 第一次入口 , 后续的入口 对于每个判断,有两个出口:exit跳出循环, 继续循环

1 第一次入口满足断言 2 每次判断继续循环满足断言

我们可以得出结论: 出口必然满足断言

- 判断不改变断言
- 每个入口都满足断言
可以推出exit满足断言

如何形式化证明​

如果证明,或者如何抽象出这个证明或者我们找到一个同构的问题

循环不变式核心是 满足约束: 1 初始化条件满足断言 2 每次迭代后满足断言 3 循环是可计算的(不是死循环)

其实3只是为了不会死循环,核心条件是1和2

crf

· 2 min read

一点也不懂nlp的我

吉布斯分布​

Hammersley-Clifford_Theorem​

损失函数​

crf​

计算参数的方式​

crf 的参数非常多,怎么求呢? 通过最大似然估计

最大似然函数的本质是什么?

本质就是: 已知统计的分布 , 那么我们假定我们统计到的数据是最大可能出现的.那么这个最大的概率对应的参数就是我们想要的参数

拟牛顿法

标注方式​

函数​

Y = { B , M , E , S}
X = {今,天,天,气,真, 热}

liner crf 参数求解​

如何训练​

  • 标注 我们要怎么标注呢? 比如我有两个人民日报的句子
// 句子1 
全总/j  致/v  全国/n  各族/r  职工/n  慰问信/n  
// 句子2
勉励/v  广大/b  职工/n  发挥/v  工人阶级/n  主力军/n  作用/n  ，/w  为/p  企业/n  改革/vn  发展/vn  建功立业/l

怎么标注呢

下面是例子

// 句子1
全/B 总/E 致/S 全/B 国/E  各/B 族/E 职/B 工/E  慰/B 问/M 信/E
// 句子2
勉/B 励/E  广/B 大E  职/B 工/E  发/B 挥/E  工/B 人/M 阶/M 级/E  主/B 力/M 军/E  作/B 用/E  ，/S  为/S  企/B 业/E  改/B 革/E  发/B 展/E  建/B 功/M 立/M 业/E

参数估计 $$ P(Y|X) = \frac{P(x,y)}{P(x)} \\\\=\frac{1}{Z(X)} e^{\sum_{n=1}^{20} n^{2}} $$

我的es之旅

· 2 min read

分词​

什么是分词,分词是一个分类问题,一般是基于权重判断是否是需要切分.机器是识别不了文字的,所以只是一个权重的切分

分词会发生在两个步骤: 写入doc , 查询query

在lucene的堆栈一般是这样的,最后调用的是incrementToken 接口

incrementToken:147, StandardTokenizer (org.apache.lucene.analysis.standard)
incrementToken:37, LowerCaseFilter (org.apache.lucene.analysis)
incrementToken:51, FilteringTokenFilter (org.apache.lucene.analysis)
fillCache:91, CachingTokenFilter (org.apache.lucene.analysis)
incrementToken:70, CachingTokenFilter (org.apache.lucene.analysis)
createFieldQuery:318, QueryBuilder (org.apache.lucene.util)
createFieldQuery:257, QueryBuilder (org.apache.lucene.util)
newFieldQuery:468, QueryParserBase (org.apache.lucene.queryparser.classic)
getFieldQuery:457, QueryParserBase (org.apache.lucene.queryparser.classic)
handleBareTokenQuery:824, QueryParserBase (org.apache.lucene.queryparser.classic)
Term:494, QueryParser (org.apache.lucene.queryparser.classic)
Clause:366, QueryParser (org.apache.lucene.queryparser.classic)
Query:251, QueryParser (org.apache.lucene.queryparser.classic)
TopLevelQuery:223, QueryParser (org.apache.lucene.queryparser.classic)
parse:136, QueryParserBase (org.apache.lucene.queryparser.classic)

搜索​

搜索的原理是 倒排+权重 ,然后取出权重最高的前几个,所以也可以看成是一个权重分类问题.

高可用​

// todo

冗余​

// todo

错误转移​

// todo

lucence​

lucence 的源码有简单的例子,主要分成三个部分

- 1 索引
    - 1.1分词
- 2 存储
    - Lucene有很多类,不过我抽象成存储应该不过分,这个我没有仔细看

- 3 搜索
    - 3.1 计算权重(一般是idf-td)

我还没用仔细看es的内容,不过根据我编译原理的理解,es就是在上面加一层parse然后转换成相应的操作

相关阅读​