發(fā)現(xiàn)一個賊有意思的新項目！
大家好，我是魚皮。最近看到一個非常有意思的項目親戚計算器，感覺很不錯，今天分享給大家。
注意：下文中的我指原項目作者
原文鏈接：https://juejin.cn/post/7203734711779196986
《親戚計算器》大概是我迄今為止寫過最復雜的算法了，它可能看起來它好像邏輯簡單，僅 1 個方法調(diào)用而已，卻耗費了我大量的時間！
從一開始靈光乍現(xiàn)，想到實現(xiàn)它的初步思路，到如今開源已 7 年多了。這期間，我一直在不斷更新才讓它日趨完善，它的工作不僅是對數(shù)據(jù)的整理，還有我對程序邏輯的梳理和設計思路的推敲。
如果你也對傳統(tǒng)文化稍微有點興趣，不妨耐心的看下去……也許你會發(fā)現(xiàn)：原來我們?nèi)粘Ａ曇詾槌５囊粋€稱呼，需要考慮那么多細節(jié)。
稱謂系統(tǒng)的龐大
中國的親戚稱呼系統(tǒng)復雜在于，它對每種親戚關系都有特定的稱呼，同時對于同種關系不同地方、對于不同性別的人都可能有不同的稱呼。
對外國人而言，父母的兄弟姐妹不外乎：uncle、aunt；而對于我們來說，父母的兄弟姐妹有：伯父、叔叔、姑姑、舅舅、姨媽；
不同地方對同個親戚的稱呼都是不一樣的，以爸爸為例，別稱包含有：爸爸、父親、老爸、阿爸、老竇、爹地、老漢、老爺子等等；
不同關系鏈可能具有相同的稱呼；比如“舅公”一詞，可以是父母親的舅舅，也可以是老公的舅舅，而這兩種關系輩分卻不同。究其原因我猜測是，傳統(tǒng)上由姻親產(chǎn)生的親戚關系，為表達謙卑會自降一輩，隨子女稱呼配偶的長輩。
一個稱呼中可能是多種關系的合稱。比如：“父母”、“子女”、“公婆”，他們不是指代一個人物關系，而是幾個關系的合稱。
在設計這套算法的時候，我希望它能盡量包含各種稱呼、各種關系鏈，因為我之所以做這個項目就是像讓它真正集合多種需求，否則如果它不夠全面那終究是個代碼演示而已。
關系網(wǎng)絡的表達
親戚的關系網(wǎng)絡是以血緣和婚姻為紐帶聯(lián)系在一起的，每個節(jié)點都是一個人，每個人都有諸如：父、母、兄、弟、姐、妹、子、女、夫、妻這樣的基礎關系。關系網(wǎng)絡中的節(jié)點數(shù)量隨著層級的加深而指數(shù)增長！如果是5層關系，大概就有9x9x9x9x9 = 59049種關系了（當然，這其中有小部分是重復的）。如果想要把幾萬個關系，數(shù)十萬個稱呼全部盡收其中顯然是不可能的，沒人有那個精力去維護。
如何將親戚關系網(wǎng)絡中每個節(jié)點之間的關系用數(shù)據(jù)結(jié)構表現(xiàn)出來是一個難點。它需要保證數(shù)據(jù)量盡量全、占用體積小、易檢索、可擴展等特點，這樣才能保證算法檢索關系時的完整性和高效性。
網(wǎng)絡的尋址問題
既然是計算，那一定不是簡單通過父、母、子、女等這些基礎關系找對應稱呼了。否則這就是簡單的字典查詢而已，談不上算法。
如果問的是：“舅媽的兒子的奶奶的外孫”又該如何呢？首先，需要在網(wǎng)絡中找到單一稱呼，如“舅媽”，而下一步找她的“兒子”，而非你自己的“兒子”。這就要求有類似于指針的功能，關系鏈每往前走一步，指針就指引著關系的節(jié)點，最終需找到答案。
而就像前面說到的一樣，某些稱謂可能對應多條關系，同時有些關系并不是唯一的。比方說你爸爸的兒子就是你嗎？有沒有可能是弟弟或者哥哥？而這些是不是同時取決于你的性別呢？
因為如果你是女的，那么你爸爸的兒子必然不是你呀！
這就對算法提出了一個要求，它必須準確的包含多種可能性。
年齡和性別的推測
隨著關系鏈的復雜，最終得到的答案也有多種。那有沒有一種可能，在對關系鏈的描述中是否存在一些詞，可以通過邏輯判斷知道對方的性別或年紀大小，進而排除一些不可呢？
例如“愛人的婆婆的兒子”，單從“愛人”二字我們并不能推測自己的性別，而后的“婆婆”確是只有女性才有的親戚，“愛人的婆婆”就足以推斷自己是男的，那么“愛人的婆婆的兒子”必然包含自己。
相反，“愛人的婆婆的女兒”一定不是自己，只能是自己的姊妹。
再比如：自己哥哥的表哥也是你的表哥，你弟弟的表哥還是你表哥嗎？因為你無法判斷你弟弟和他的表哥誰大，自然無法判斷對方是你的表哥還是表弟。既然都有可能存在，就需要保留可能性進一步計算。這就涉及到了在關系鏈的計算中不僅僅需要考慮隱藏的性別線索，還有年齡線索。
身份角度的切換
單從親戚和自己的關系鏈條中開始算親戚的稱呼，僅僅是單向的推算，只需要一個個關系往下算就好。如果想知道對方稱呼為我什么，這就需要站在對方的角度，重新逆向的調(diào)理出我和他之間的關系了。比如我的“外孫”應該叫我什么？
另一方面，如果把我置身于第三者，想知道我的兩個親戚他們之間如何稱呼，就必須要同時站在兩個親戚的角度，看待他們彼此之間的關系了。比如：我的“舅媽”該叫我的“外婆”什么呢？
年齡排序的問題
前面說到的都是對不同關系鏈中的可能性推敲，那如果相同的關系如何判斷年齡呢？如果你有3個舅舅呢？雖然不管哪個舅舅，他們對于你的關系都一樣，他們的老婆你都得叫聲“舅媽”。但他們畢竟有年齡區(qū)別，自然就有長幼的排序了。有了排序，就又引發(fā)了對他們之間關系的思考。
還是舉例說明下：“舅舅”和“舅媽”是什么關系？相信大部分第一反應就是夫妻關系唄！其實不盡然，畢竟有些人不會只有一個舅舅吧？那“大舅媽”和“二舅”就不是夫妻關系了，他們是叔嫂關系呀。“二舅”得管“大舅媽”叫“嫂子”，“大舅媽”得管“二舅”叫“小叔子”。
再進一步說，“二舅的兒子”得叫“大舅媽”為“伯母”，“大舅的兒子”得叫“二舅”為“二叔”。這些由父輩的排序問題影響自己稱謂的不同，而是我這套算法需要考慮的內(nèi)容。
怎么樣？是不是沒有想象中的那么簡單？
項目線上訪問地址：https://passer-by.com/relationship/
項目源碼：https://github.com/mumuy/relationship
算法實現(xiàn)原理介紹
常見問題
市面上同類型的算法基本以 “稱謂-直接關系-稱謂” 的方式實現(xiàn)，如：
"爸爸": {
"爸爸": "爺爺",
"媽媽": "奶奶",
"哥哥": "伯父",
"弟弟": "叔叔",
"姐姐": "姑媽",
"妹妹": "姑媽",
"丈夫": "未知",
"妻子": "媽媽",
"兒子": {"older": "哥哥", 'middle': "我", "younger": "弟弟"},
"女兒": {"older": "姐姐", 'middle': "我", "younger": "妹妹"}
}
這樣的結(jié)構主要有以下問題：
無法跨代直接查詢，如：如何知道“舅媽的婆婆”是誰？ 無法逆向查詢稱謂，如：“表哥的媽媽”的媽媽是“舅媽”、“姨媽”還是“姑媽”？ 數(shù)據(jù)結(jié)構過于臃腫, 如：某個節(jié)點下可能會出現(xiàn)多個“未知” 無法兼容多種稱呼，如：各地稱呼不盡相同，“爸爸”也可以叫“父親”、“爹地” 無法進行關系拓撲，如：“舅媽”和我什么關系？
本算法的原理
采用 “關系鏈-稱謂集合” 哈希對的方式建立數(shù)據(jù)庫，映射親戚網(wǎng)絡中的每個節(jié)點和自己的關系
數(shù)據(jù)結(jié)構
'h':['老公','丈夫','先生','官人','男人','漢子','夫','夫君','相公','夫婿','愛人','老伴'],
'h,f':['公公','翁親','老公公'],
每個稱謂都可以找到相應的關系鏈，每個關系鏈同時有對應的稱謂集合，這里需要引入自己“發(fā)明”的特殊語法標記
語法說明
【關系】f:父,m:母,h:夫,w:妻,s:子,d:女,xb:兄弟,ob:兄,lb:弟,xs:姐妹,os:姐,ls:妹
【修飾符】 1:男性,0:女性,&o:年長,&l:年幼,#:隔斷,[a|b]:并列
例如：
"f"對應著爸爸，那么："f,m"對應著奶奶,"f,f"對應著爺爺；
這樣在查詢關系的時候，只需要對關系鏈進行計算就好了，而不是對稱謂進行字典查找
算法思路
當用戶輸入“舅媽的婆婆”，可以分解出兩個對象“舅媽”和“婆婆”（前者的婆婆）
從“關系鏈-稱謂集合”映射關系可知，這兩個對象的關系鏈分別是："m,xb,w"和"h,m",合并后的關系即："m,xb,w,h,m"
此時關系鏈會出現(xiàn)冗余，需要進一步處理：
"w,h"表示“老婆的老公”，即自己，可直接將關系鏈簡化成："m,xb,m"
同理，"xb,m"表示“兄弟的媽媽”，即自己的媽媽，可將關系鏈再次簡化為："m,m"
當無法進一步簡化時，就得到了“最簡關系鏈”，將其帶入親戚關系數(shù)據(jù)庫查詢，便可知"m,m"即為自己的“外婆”
這樣就將復雜的關系鏈轉(zhuǎn)換成直接關系了，除此之外還可根據(jù)“關系鏈-稱謂集合”反向通過稱呼找到關系；
實現(xiàn)細節(jié)
如何實現(xiàn)關系鏈的簡化？
關系鏈為字符串，用正則表達式即可按情形匹配，同時做到“替換”的操作。由于所有非直接的關系，都是存在關系鏈表達的冗余。雖然冗余可能多層且復雜，只需要考慮兩層關系中的去冗余，反復處理即可。
某些多層關系可能未必對應一種關系，如何解決關系的不唯一？
“爸爸的兒子”不一定是自己，也可能是自己的兄弟。在語法中引入了“隔斷”和“并列”語法，可以借助正則表達式將此類不唯一的關系拆分為多組，每次再單獨帶入遞歸求最簡解即可。
每個節(jié)點離自己遠一層關系，節(jié)點數(shù)據(jù)便翻倍，如何解決數(shù)據(jù)量過大的問題？
中國的親戚關系存在一定規(guī)律，旁系分支大體由 分支節(jié)點 及其 子代關系 ，我們只需記錄 分支節(jié)點 和 子代關系 即可。如：“舅表哥”和“堂哥”兩者在和自己的關系鏈上存在一定相似，沒必要記錄兩者所有關系。只需知道“舅表哥”是“舅舅”的后代，而“堂哥”是“叔伯”的后代，那么“舅表哥”和“堂哥”的所有后代及姻親數(shù)據(jù)可以只存3部分。即：
舅表哥關系數(shù)據(jù) = 舅舅（分支節(jié)點） + 哥哥關系數(shù)據(jù)（子代關系）；
堂哥關系數(shù)據(jù) = 叔伯（分支節(jié)點） + 哥哥關系數(shù)據(jù)（子代關系）；
這樣的關系有很多，如：“舅表”、“姑表”、“從堂”、“姑表叔表”等等，對關系數(shù)據(jù)進行拆分復用，即可以達到壓縮數(shù)據(jù)量。同時在腳本運行中對 分支節(jié)點 和 子代關系 進行拼接即可組合出數(shù)據(jù)庫。
你還知道哪些可以計算出親戚關系的好方法，歡迎在評論區(qū)留言~
最后，歡迎學編程的朋友們加入魚皮的 編程知識星球 ，魚皮會 1 對 1 解決你的問題，直播帶你做出項目、為你定制學習計劃和求職指導，還能獲取海量編程學習資源，和上萬名學編程的同學共享知識、交流進步。求職季一起加油！
往期推薦