At present, the “kinship” algorithm in the market mainly adopts the way of appellation – direct relation – appellation to search
The data structure
‘Dad ‘: {
‘Papa ‘:’ Grandpa ‘,
‘Mama ‘:’ Grandma ‘,
‘Brother ‘:’ uncle ‘,
‘Brother ‘:’ uncle ‘,
‘Sister ‘:’ aunt ‘,
‘Sister ‘:’ aunt ‘,
Husband: Unknown,
‘Wife ‘:’ Mother ‘,
‘son’ : {‘ older ‘:’ brother ‘, ‘middle’ : ‘I’, ‘younger’ : ‘brother’},
‘daughter’ : {‘ older ‘:’ sister ‘, ‘middle’ : ‘I’, ‘younger’ : ‘sister’}
}
Such a structure mainly has the following problems:
1. The compound relationship such as “aunt’s mother-in-law” cannot be queried directly;
2. The appellation can not reverse query, such as: “cousin’s mother” mother is “aunt”, “aunt” or “aunt”?
3. The data structure is poor and the data is bloated. Multiple “unknowns” appear in attention
4. Not compatible with multiple titles, such as “dad” can also be called “father” or “daddy”
5. The relationship topology cannot be carried out, for example: What is the relationship between “aunt” and me?
And I used this algorithm is: relation chain – the way of appellation set search
Demo address: passer-by.com/relationshi…
Project address: github.com/mumuy/relat…
The data structure
‘h’ : [‘ husband ‘, ‘husband’, ‘Sir,’ officer person ‘, ‘man’, ‘the man’, ‘, ‘, ‘husband’, ‘” xianggong “‘, ‘husband’, ‘love’, ‘his wife].
‘h,f’:[‘ father-in-law ‘,’ weng qin ‘,’ old father-in-law ‘],
Each appellation can find a corresponding relation chain, and each relation chain has a corresponding address set at the same time. Here, we need to introduce special grammatical marks of our “invention”
Grammar specification
[relations] f: father, m: mother, h:, w: wife, s: son, d: female, xb: brother, ob: brother, lb: younger brother, xs: sister, OS: elder sister, ls: younger sister
Modifier 】 【 1: male, 0: women, & o: older, & l: young, # : partition, (a | b) :
Such as:
“F” for dad, so “F, M” for grandma,” F, F “for grandpa;
In this way, when querying the relation, only need to calculate the relation chain, rather than dictionary lookup of the appellation
Algorithm ideas
1. When users input “Auntie’s mother-in-law”, two objects can be decomposed “Auntie” and “mother-in-law” (the former’s mother-in-law)
2. From the mapping relation of “relation chain – appellation set “, it can be seen that the relation chain of these two objects is” M, Xb, W “and” H, M “respectively, and the merged relation is” M, Xb, W, H, M “.
3. At this time, there will be redundancy in the relationship chain, such as:
“W, H” stands for “wife’s husband”, that is, oneself! We can simply simplify the chain of relationships to: “m,xb,m”.
In the same way, there is another layer of redundancy, “Xb,m” for” brother’s mother “, that is, one’s own mother! So the chain of relations can be further simplified to: “m,m”
4. At this time, the complex relationship chain into direct relationship, direct query “relationship chain – appellation set” mapping relationship is good
implementation
1. The mapping relation of “relation chain – appellation set” can be expressed by the key-value pair of JSON object, that is, the attribute is the corresponding relation chain and the value is the appellation set. Key – value pairs have the advantage of fast query speed.
2. The simplified calculation of the relation chain can be realized by the way of regular matching. The rules only need to consider the simplification of the two-layer relation and be processed for many times until they can no longer be simplified.
For example: father’s wife is mother, brother’s father is father, wife’s husband is himself and so on
And of course, there’s gender, and there’s multiple possibilities
The mother of a son, your wife when you are male, yourself when you are female; Mother’s son could be you or your brother, and when you’re a woman, it can only be your brother.
This is all about matching conditions in the regular expression and then replacing them! That’s why you’ve introduced modifiers in your syntax tags.
#: partition, partition is the whole chain of relationships
[] a | b: parallel, separate is a single node in chain
They all use:
ZhaXunWang ip138.com/
Online enquiry qinshu.supfree.net/
Online tool atool.org/
Youdao language talent dict.youdao.com/k12yuwen/ht…
Mi MIUI system calculator www.miui.com/