中国亲戚关系计算算法

[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
“我一份数据不可能存两种方式的” 为什么？空间换取时间啊，而且这里的字典数据又不会变

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

[mumuy]

@zhy0216 如果我把空间换成了时间，在程序里面空间就是文件大小，文件的加载本身就是需要时间的，到头来我并不会占到便宜；软件开发我还需要考虑维护成本问题，如果一份数据有两种格式，本身就造成了维护的压力也容易出错，两种格式程序就要有两个参照，如果出错了以谁为主？

[mccoymir]

这个.....老婆的妹妹的老公 = 小姨夫 @_@

[mumuy]

@mccoymir 你要区分“小姨夫”和“小姨父”的区别啦～

[mumuy]

@zhy0216 哈哈哈，一起讨论当然是好事！开源就是这个目的呀，我的意思是说明我为什么不那么做

[zhy0216]

@mumuy 我觉得你可能还是没看明白我的意思
第二种数据格式你可以用几行代码生成出来的. 不是指程序的文件大小，而是使用内存的大小

[Nott]

只关注结果，小时候寄读于姑姑家，天天跟姑父的侄子们打交道，于是一查：爸爸的姐姐的老公的弟弟的儿子：貌似他 /她跟你不是很熟哦!

[ningbo16]

[littiefish]

@Nott 用三姑六婆试了下，你这个有两个称呼，姻兄 /姻弟。。。

[Level5]

为什么选择了性别以后就不能选“夫或妻”了？你叫同 x 志情何以堪？

[qiayue]

@Nott 这是计算亲戚关系不是算命

[Humorce]

@Level5 同性婚姻本身就违背了这一套称呼系统。

[Nott]

@littiefish #28 我很怀疑生活中的通俗称呼中是否有这种称呼。

[Telegram]

@Nott #26 照道理算，确实是没啥亲戚关系

[Level5]

@humorce 所以人们就说违背伦 x 咯？

[mumuy]

@ningbo16 输入“舅姥爷的外甥女”，外甥女不加数字，因为我们一般对长辈才加数字，表示大小

[mumuy]

@Level5 哈哈哈，我没说同性不可以啊！谁说“妻”就是女的了？？

[mumuy]

@Nott 所以你觉得你姑丈的侄子和你什么关系？如果表达得出来，我可以加数据库啊

[Nott]

@mumuy #37 就是表达不出正式的通俗称谓，才去查了一下

[mumuy]

@Nott 因为这种情况你们只是认识，并不代表就有亲戚关系

[mumuy]

@Nott 你们是通过亲戚的关系认识，不一定是亲戚关系

[jiangzhuo]

这个不方便啊，就不能搞个那种输入对方名字或者身份证号直接出关系的。

[WAITUNG]

WHAT ？过不了 QQ 安全验证？ 红色感叹号

[mumuy]

@jiangzhuo 呵呵呵，有这个那狗仔都失业了

[xfspace]

App 放百度盘下载贼麻烦，来个直接的链接，谢谢～

[yingfengi]

@mumuy 虽不明。但觉厉
顺便问一句：小米有联系过你吗。。。

[mumuy]

@yingfengi 没有啊，本来就是开源的，可以比较随意用

[cpdyj0]

挖个坟，，想问下是不是可以用图实现（查表），我想下：

小米计算器可选择的关系有 10 种，
那么一个人一个节点就有 10 个对外的箭头。（我还没学过图论不懂得怎么说）
然后把能找到的称呼全部填进去，按照用户的点击跟踪就行了，也容易反向计算。