中国亲戚关系计算算法

[mumuy]

刚刚看到网友关于亲戚关系算法的问题 [分享一个亲属关系的算法] ： https://www.v2ex.com/t/408080#reply10

说道还差一个程序员实现，哈哈哈，看到我异常兴奋！因为…………我已经写完了～ 顺便打个广告

算法原理： http://www.jianshu.com/p/74290f1ae838

算法实现： http://passer-by.com/relationship/

开源代码： https://github.com/mumuy/relationship

[mumuy]

不知道对方写成论文会不会被怀疑抄袭……我的算法是去年写的

[mohoumk2]

你需要个小米内置的亲戚关系计算器

[mumuy]

@mohoumk2 小米内置的那个用的就是我的开源代码啊！不信你可以分析它的网页版本： http://www.miui.com/zt/calculator2016/dist.php

[jasontse]

没有人记得「三姑六婆」

[chuanqirenwu]

他那算法不实用，只能做理论分析，或者作为你这个算法的前序处理。

[mumuy]

@jasontse 记得呀，计算器的想法我是看到了这个 APP 的，但是算法是我自己写的，和它的思路不一样，你可以在我的算法原理文章内看到我说的不一样在哪里

[mumuy]

@chuanqirenwu 感觉写成论文不合适了，没有具体阐明怎么实现，而且我的程序处理的问题更复杂。关键是，我的算法去年就开源了………

[czheo]

@chaoxu 踢馆的来啦！

[linKnowEasy]

点个赞, 比较喜欢这种 生活 代码化 的处理

[zhy0216]

有向图 + 一堆数据 应该可以解决

`2.从“关系链-称谓集合”映射关系可知，这两个对象的关系链分别是："m,xb,w"和"h,m",合并后的关系即："m,xb,w,h,m"`

你的数据结构是不是需要 inverted index 下 会快一些

[mumuy]

@zhy0216 现在用那个程序很慢吗？主要考虑问题是同一个关系链有多种称呼，一个称呼有多种关系链；比如外婆也可以叫成姥姥，表哥有舅家的姑家的姨家的

[zhy0216]

没用过。。。 只是理论上而已
字典可以有多个 key 对应同一个 value 的

[mumuy]

@zhy0216 我的意思是现在还有一个 value 对应多个 key 的情况

[zhy0216]

我的意思可以调换一下 key-value
比如这样 {ab: [cc, dd]} => {cc: ab, dd: ab}
因为你查的是 cc，dd 第一种字典最坏的情况需要遍历所有的 value， 第二种一般认为是 O(1)

[mumuy]

@zhy0216 我的意思是{ab: [cc, dd],cd:[cc]} => {cc: ab, dd: ab}你要怎么办？？？？

[mumuy]

@zhy0216 我的意思是{ab: [cc, dd],cd:[cc]}怎么办？ cc 在多个地方出现，而且不用遍历数组的，直接 indexOf 就好

[chaoxu]

@mumuy 我很高兴也有人想过这个问题. 但你有些评论并不适用于我们领域.

"感觉写成论文不合适了"
写成论文是否合适这个应该是学术界内的人评判.

"没有具体阐明怎么实现"
做理论的关心的是算法的理论复杂度. 我们并不关心是否真的写成一个程序. 如果有程序员写出来那是极好的. 但那不是我们的工作.

"而且我的程序处理的问题更复杂。"
我不知道你有没有看整个文章. 我们解决的不是同一个问题, 我们解决的是一个抽象的问题.
我在社交网络上所给的例子都是简单易懂的简化版, 所有词语都是相同权值的.
每个词语可以有不同权值, 我们要找的是最短的路径. 而且我的算法是适用于 sudanese pattern 的, 并没有专门对应中文亲属关系.
但是这都不是为什么我们发 paper. 重要的来自于我们证明了算法的复杂度和正确性(而正确性本身需要定义问题是什么).

"关键是，我的算法去年就开源了………"
这是我的疏忽, 没有发现你的这个程序. 等 IPL 那边 review 过后, 会在 introduction 的提到你的 library. 因为你超越了我们说的现有的两个 benchmark 的弱点(三姑六婆和小米内置计算器, 其实蛮奇怪的因为你提到内置用的就是你的系统).
但是, 你的程序不能解决我们要解决的问题.

[zhy0216]

@mumuy
indexOf 就是 O(n)

1. 原先的字典 里面可以是 set，可能考虑到 js 没有 set 用的 list
2. 按你说的情况 {ab: [cc, dd],cd:[cc]} => {cc: [ab, cd], dd: [ab]}

[mumuy]

@zhy0216 但是我算完回来还要把结果翻译一遍啊，比如算完是 ab,你不还得一样查一遍吗？？？我一份数据不可能存两种方式的

[zhy0216]

@mumuy
“我一份数据不可能存两种方式的” 为什么？空间换取时间啊，而且这里的字典数据又不会变

当然，实际情况可能你是对的 我也只是提出一个可能性