V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
mumuy
V2EX  ›  分享创造

中国亲戚关系计算算法

  •  
  •   mumuy ·
    mumuy · 2017-11-24 11:20:36 +08:00 · 7645 次点击
    这是一个创建于 2316 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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

    47 条回复    2018-11-13 22:06:02 +08:00
    mumuy
        1
    mumuy  
    OP
       2017-11-24 11:34:14 +08:00
    不知道对方写成论文会不会被怀疑抄袭……我的算法是去年写的
    mohoumk2
        2
    mohoumk2  
       2017-11-24 11:35:38 +08:00 via Android   ❤️ 1
    你需要个小米内置的亲戚关系计算器
    mumuy
        3
    mumuy  
    OP
       2017-11-24 11:39:41 +08:00   ❤️ 2
    @mohoumk2 小米内置的那个用的就是我的开源代码啊!不信你可以分析它的网页版本: http://www.miui.com/zt/calculator2016/dist.php
    jasontse
        4
    jasontse  
       2017-11-24 11:41:18 +08:00 via iPad   ❤️ 1
    没有人记得「三姑六婆」
    chuanqirenwu
        5
    chuanqirenwu  
       2017-11-24 11:42:53 +08:00
    他那算法不实用,只能做理论分析,或者作为你这个算法的前序处理。
    mumuy
        6
    mumuy  
    OP
       2017-11-24 11:43:46 +08:00
    @jasontse 记得呀,计算器的想法我是看到了这个 APP 的,但是算法是我自己写的,和它的思路不一样,你可以在我的算法原理文章内看到我说的不一样在哪里
    mumuy
        7
    mumuy  
    OP
       2017-11-24 11:49:40 +08:00
    @chuanqirenwu 感觉写成论文不合适了,没有具体阐明怎么实现,而且我的程序处理的问题更复杂。关键是,我的算法去年就开源了………
    czheo
        8
    czheo  
       2017-11-24 11:50:35 +08:00
    @chaoxu 踢馆的来啦!
    linKnowEasy
        9
    linKnowEasy  
       2017-11-24 11:51:53 +08:00
    点个赞, 比较喜欢这种 生活 代码化 的处理
    zhy0216
        10
    zhy0216  
       2017-11-24 12:06:37 +08:00
    有向图 + 一堆数据 应该可以解决

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

    你的数据结构是不是需要 inverted index 下 会快一些
    mumuy
        11
    mumuy  
    OP
       2017-11-24 12:12:59 +08:00
    @zhy0216 现在用那个程序很慢吗?主要考虑问题是同一个关系链有多种称呼,一个称呼有多种关系链;比如外婆也可以叫成姥姥,表哥有舅家的姑家的姨家的
    zhy0216
        12
    zhy0216  
       2017-11-24 12:18:33 +08:00
    没用过。。。 只是理论上而已
    字典可以有多个 key 对应同一个 value 的
    mumuy
        13
    mumuy  
    OP
       2017-11-24 12:25:20 +08:00
    @zhy0216 我的意思是现在还有一个 value 对应多个 key 的情况
    zhy0216
        14
    zhy0216  
       2017-11-24 12:28:21 +08:00
    我的意思可以调换一下 key-value
    比如这样 {ab: [cc, dd]} => {cc: ab, dd: ab}
    因为你查的是 cc,dd 第一种字典最坏的情况需要遍历所有的 value, 第二种一般认为是 O(1)
    mumuy
        15
    mumuy  
    OP
       2017-11-24 13:12:19 +08:00
    @zhy0216 我的意思是{ab: [cc, dd],cd:[cc]} => {cc: ab, dd: ab}你要怎么办????
    mumuy
        16
    mumuy  
    OP
       2017-11-24 13:13:50 +08:00
    @zhy0216 我的意思是{ab: [cc, dd],cd:[cc]}怎么办? cc 在多个地方出现,而且不用遍历数组的,直接 indexOf 就好
    chaoxu
        17
    chaoxu  
       2017-11-24 13:15:45 +08:00
    @mumuy 我很高兴也有人想过这个问题. 但你有些评论并不适用于我们领域.

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

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

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

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

    1. 原先的字典 里面可以是 set,可能考虑到 js 没有 set 用的 list
    2. 按你说的情况 {ab: [cc, dd],cd:[cc]} => {cc: [ab, cd], dd: [ab]}
    mumuy
        19
    mumuy  
    OP
       2017-11-24 13:50:04 +08:00
    @zhy0216 但是我算完回来还要把结果翻译一遍啊,比如算完是 ab,你不还得一样查一遍吗???我一份数据不可能存两种方式的
    zhy0216
        20
    zhy0216  
       2017-11-24 14:07:19 +08:00
    @mumuy
    “我一份数据不可能存两种方式的” 为什么?空间换取时间啊,而且这里的字典数据又不会变

    当然,实际情况可能你是对的 我也只是提出一个可能性
    mumuy
        21
    mumuy  
    OP
       2017-11-24 14:15:11 +08:00
    @zhy0216 如果我把空间换成了时间,在程序里面空间就是文件大小,文件的加载本身就是需要时间的,到头来我并不会占到便宜;软件开发我还需要考虑维护成本问题,如果一份数据有两种格式,本身就造成了维护的压力也容易出错,两种格式程序就要有两个参照,如果出错了以谁为主?
    mccoymir
        22
    mccoymir  
       2017-11-24 14:15:35 +08:00
    这个.....老婆的妹妹的老公 = 小姨夫 @_@
    mumuy
        23
    mumuy  
    OP
       2017-11-24 14:24:21 +08:00
    @mccoymir 你要区分“小姨夫”和“小姨父”的区别啦~
    mumuy
        24
    mumuy  
    OP
       2017-11-24 14:25:07 +08:00
    @zhy0216 哈哈哈,一起讨论当然是好事!开源就是这个目的呀,我的意思是说明我为什么不那么做
    zhy0216
        25
    zhy0216  
       2017-11-24 14:50:51 +08:00
    @mumuy 我觉得你可能还是没看明白我的意思
    第二种数据格式你可以用几行代码生成出来的. 不是指程序的文件大小,而是使用内存的大小
    Nott
        26
    Nott  
       2017-11-24 15:03:21 +08:00
    只关注结果,小时候寄读于姑姑家,天天跟姑父的侄子们打交道,于是一查:爸爸的姐姐的老公的弟弟的儿子:貌似他 /她跟你不是很熟哦!
    ningbo16
        27
    ningbo16  
       2017-11-24 15:13:37 +08:00
    littiefish
        28
    littiefish  
       2017-11-24 15:13:53 +08:00
    @Nott 用三姑六婆试了下,你这个有两个称呼,姻兄 /姻弟。。。
    Level5
        29
    Level5  
       2017-11-24 15:42:12 +08:00
    为什么选择了性别以后就不能选“夫或妻”了?你叫同 x 志情何以堪?
    qiayue
        30
    qiayue  
       2017-11-24 15:45:03 +08:00
    @Nott 这是计算亲戚关系不是算命
    Humorce
        31
    Humorce  
       2017-11-24 15:45:20 +08:00 via iPhone
    @Level5 同性婚姻本身就违背了这一套称呼系统。
    Nott
        32
    Nott  
       2017-11-24 15:46:50 +08:00
    @littiefish #28 我很怀疑生活中的通俗称呼中是否有这种称呼。
    Telegram
        33
    Telegram  
       2017-11-24 15:48:05 +08:00
    @Nott #26 照道理算,确实是没啥亲戚关系
    Level5
        34
    Level5  
       2017-11-24 15:58:11 +08:00
    @humorce 所以人们就说违背伦 x 咯?
    mumuy
        35
    mumuy  
    OP
       2017-11-24 15:58:40 +08:00
    @ningbo16 输入“舅姥爷的外甥女”,外甥女不加数字,因为我们一般对长辈才加数字,表示大小
    mumuy
        36
    mumuy  
    OP
       2017-11-24 16:00:08 +08:00
    @Level5 哈哈哈,我没说同性不可以啊!谁说“妻”就是女的了??
    mumuy
        37
    mumuy  
    OP
       2017-11-24 16:01:17 +08:00
    @Nott 所以你觉得你姑丈的侄子和你什么关系?如果表达得出来,我可以加数据库啊
    Nott
        38
    Nott  
       2017-11-24 16:15:44 +08:00
    @mumuy #37 就是表达不出正式的通俗称谓,才去查了一下
    mumuy
        39
    mumuy  
    OP
       2017-11-24 16:18:33 +08:00
    @Nott 因为这种情况你们只是认识,并不代表就有亲戚关系
    mumuy
        40
    mumuy  
    OP
       2017-11-24 16:19:00 +08:00
    @Nott 你们是通过亲戚的关系认识,不一定是亲戚关系
    jiangzhuo
        41
    jiangzhuo  
       2017-11-24 18:22:33 +08:00
    这个不方便啊,就不能搞个那种输入对方名字或者身份证号直接出关系的。
    WAITUNG
        42
    WAITUNG  
       2017-11-24 18:55:14 +08:00
    WHAT ?过不了 QQ 安全验证? 红色感叹号
    mumuy
        43
    mumuy  
    OP
       2017-11-24 21:10:21 +08:00
    @jiangzhuo 呵呵呵,有这个那狗仔都失业了
    xfspace
        44
    xfspace  
       2017-11-24 21:47:33 +08:00 via Android
    App 放百度盘下载贼麻烦,来个直接的链接,谢谢~
    yingfengi
        45
    yingfengi  
       2017-11-24 23:34:45 +08:00 via Android
    @mumuy 虽不明。但觉厉
    顺便问一句:小米有联系过你吗。。。
    mumuy
        46
    mumuy  
    OP
       2017-11-27 16:19:55 +08:00
    @yingfengi 没有啊,本来就是开源的,可以比较随意用
    cpdyj0
        47
    cpdyj0  
       2018-11-13 22:06:02 +08:00
    挖个坟,,想问下是不是可以用图实现(查表),我想下:

    小米计算器可选择的关系有 10 种,
    那么一个人一个节点就有 10 个对外的箭头。(我还没学过图论不懂得怎么说)
    然后把能找到的称呼全部填进去,按照用户的点击跟踪就行了,也容易反向计算。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5295 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 09:31 · PVG 17:31 · LAX 02:31 · JFK 05:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.