Skip to content

算法实现

Jump to bottom
PASSER-BY edited this page Jan 12, 2023 · 2 revisions

常见问题

市面上同类型的算法基本以 “称谓-直接关系-称谓” 的方式实现，如：

"爸爸": {
    "爸爸": "爷爷",
    "妈妈": "奶奶",
    "哥哥": "伯父",
    "弟弟": "叔叔",
    "姐姐": "姑妈",
    "妹妹": "姑妈",
    "丈夫": "未知",
    "妻子": "妈妈",
    "儿子": {"older": "哥哥", 'middle': "我", "younger": "弟弟"},
    "女儿": {"older": "姐姐", 'middle': "我", "younger": "妹妹"}
}

这样的结构主要有以下问题：

  1. 无法跨代直接查询，如：如何知道“舅妈的婆婆”是谁？
  2. 无法逆向查询称谓，如：“表哥的妈妈”的妈妈是“舅妈”、“姨妈”还是“姑妈”？
  3. 数据结构过于臃肿, 如：某个节点下可能会出现多个“未知”
  4. 无法兼容多种称呼，如：各地称呼不尽相同，“爸爸”也可以叫“父亲”、“爹地”
  5. 无法进行关系拓扑，如：“舅妈”和我什么关系？

本算法的原理

采用 “关系链-称谓集合” 哈希对的方式建立数据库，映射亲戚网络中的每个节点和自己的关系

数据结构

'h':['老公','丈夫','先生','官人','男人','汉子','夫','夫君','相公','夫婿','爱人','老伴'],
'h,f':['公公','翁亲','老公公'],

每个称谓都可以找到相应的关系链，每个关系链同时有对应的称谓集合，这里需要引入自己“发明”的特殊语法标记

语法说明

【关系】f:父,m:母,h:夫,w:妻,s:子,d:女,xb:兄弟,ob:兄,lb:弟,xs:姐妹,os:姐,ls:妹
【修饰符】 1:男性,0:女性,&o:年长,&l:年幼,#:隔断,[a|b]:并列

例如：

"f"对应着爸爸，那么："f,m"对应着奶奶,"f,f"对应着爷爷；

这样在查询关系的时候，只需要对关系链进行计算就好了，而不是对称谓进行字典查找

算法思路

  1. 当用户输入“舅妈的婆婆”，可以分解出两个对象“舅妈”和“婆婆”（前者的婆婆）

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

  3. 此时关系链会出现冗余，需要进一步处理：

    • "w,h"表示“老婆的老公”，即自己，可直接将关系链简化成："m,xb,m"

    • 同理，"xb,m"表示“兄弟的妈妈”，即自己的妈妈，可将关系链再次简化为："m,m"

    • 当无法进一步简化时，就得到了“最简关系链”，将其带入亲戚关系数据库查询，便可知"m,m"即为自己的“外婆”

  4. 这样就将复杂的关系链转换成直接关系了，除此之外还可根据“关系链-称谓集合”反向通过称呼找到关系；

实现细节

  1. 如何实现关系链的简化？

    关系链为字符串，用正则表达式即可按情形匹配，同时做到“替换”的操作。由于所有非直接的关系，都是存在关系链表达的冗余。虽然冗余可能多层且复杂，只需要考虑两层关系中的去冗余，反复处理即可。

  2. 某些多层关系可能未必对应一种关系，如何解决关系的不唯一？

    “爸爸的儿子”不一定是自己，也可能是自己的兄弟。在语法中引入了“隔断”和“并列”语法，可以借助正则表达式将此类不唯一的关系拆分为多组，每次再单独带入递归求最简解即可。

  3. 每个节点离自己远一层关系，节点数据便翻倍，如何解决数据量过大的问题？

    中国的亲戚关系存在一定规律，旁系分支大体由 分支节点 及其 子代关系 ，我们只需记录 分支节点 和 子代关系 即可。如：“舅表哥”和“堂哥”两者在和自己的关系链上存在一定相似，没必要记录两者所有关系。只需知道“舅表哥”是“舅舅”的后代，而“堂哥”是“叔伯”的后代，那么“舅表哥”和“堂哥”的所有后代及姻亲数据可以只存3部分。即：

    舅表哥关系数据 = 舅舅（分支节点） + 哥哥关系数据（子代关系）；

    堂哥关系数据 = 叔伯（分支节点） + 哥哥关系数据（子代关系）；

    这样的关系有很多，如：“舅表”、“姑表”、“从堂”、“姑表叔表”等等，对关系数据进行拆分复用，即可以达到压缩数据量。同时在脚本运行中对 分支节点 和 子代关系 进行拼接即可组合出数据库。

Clone this wiki locally