Flatten Json
2021-08-19
0. 问题
之前在工作中遇到一个问题，我们要从客户的 API endpoint get 一些数据，然后根据具体的 field value 来做处理。
难点在于，客户 API 返回的数据格式是 json object，但是里面嵌套了很多个 json array。
比如下面这样：
- 每个 json object 都可能有 json array，json property，或者 json object；
- 每个 json array 里面也有各种不同的情况；
而我们需要做的是，先找到一个最内层的 match value，比如我要根据 key 13 来 match 3 这个 value，然后呢，再回溯跟 key 13 相关的上面一个 level 的 property value，也就是 key 13 = 3 的时候，key 5 等于几。
{
"key1": "value1",
"key2": "value2",
"key3": [
{
"key4": [
{
"key5": 1,
"key6": {
"key7": 1,
"key8": 2,
"key9": 3
},
"key10": [
{
"key11": 1,
"key12": 2,
"key13": 3
}
]
},
{
"key5": 1,
"key6": {
"key7": 1,
"key8": 2,
"key9": 3
},
"key10": [
{
"key11": 1,
"key12": 2,
"key13": 4
}
]
}
]
}
]
}
1. 抽象
这个问题可以抽象成一个多叉树的问题：
- 每个 key 就是一个 node，每个 node 有 key 和 value；
- 当 value = json array 的时候，就是以 key 为 root node 来构建一层新的 node，该 node value = null，
- 当 value = json value 的时候，这个 node 是 leaf node，既有 key 又有 value；
- 当 value = json object 的时候，我们可以直接在当前这个 level 进行 flatten，比如 key 6 有三个 property，那么这三个 property 都是 leaf node；
也就是说，我们要遍历整棵树，然后把每个 node 的路径存下来，并且通过给定一个 match-path 和 match-value，获取这个 match-node 的位置，并且能够根据这个位置，去获得这条路径上其他 node 的 value。
这里的难点在于如何处理 json array，因为你在 search 的时候不知道你需要 match 的那个 node 到底是 json array 的第几个 element，所以你只能给出一个模糊的 match-path，比如 key3[].key4[].key10[].key13 = 3，然后你需要回溯求得 key3[].key4[].key5 的值。
我们暂时先考虑 single match 的情况。
3. 举例
下面是一个 example json：
[
{
"employees": [
{
"id": 1,
"values": {
"first_name": "Luna",
"last_name": "Wen"
},
"positions": [
{
"title": "developer"
}
]
},
{
"id": 2,
"values": {
"first_name": "Luna2",
"last_name": "Wen2"
},
"positions": [
{
"title": "business analyst"
}
]
},
{
"id": 3,
"values": {
"first_name": "Luna3",
"last_name": "Wen3"
},
"positions": [
{
"title": "tester"
}
]
}
],
"update_datetime": "2020-08-14T13:52:18+10:00"
}
]
求解，当 position title = “business analyst” 时， employee first_name 是什么。
4. 代码
Step 1：把这个 json string 转换成 json token
PS: 我用的是 linqpad 来做 demo。
首先要把这个 json 的双引号都变成两个双引号。
然后 declare static variable。
static string jsonString = @"
[
{
""employees"": [
{
""id"": 1,
""values"": {
""first_name"": ""Luna"",
""last_name"": ""Wen""
},
""positions"": [
{
""title"": ""developer""
}
]
},
{
""id"": 2,
""values"": {
""first_name"": ""Luna2"",
""last_name"": ""Wen2""
},
""positions"": [
{
""title"": ""business analyst""
}
]
},
{
""id"": 3,
""values"": {
""first_name"": ""Luna3"",
""last_name"": ""Wen3""
},
""positions"": [
{
""title"": ""tester""
}
]
}
],
""update_datetime"": ""2020-08-14T13:52:18+10:00""
}
]";
接下来 import 一个 json package -> Newtonsoft.Json.Linq。
然后 parse json string，转为 JToken type。
JToken token = JToken.Parse(jsonString);
Step 2：JToken To Dictionary Hierarchy
接下来我们要遍历这个 JToken，构造一个能体现出每个 value 所处位置的 dictionary。
这个 dictionary 的数据结构比较复杂，一方面我们要有一个 dictionary 来 map path 和 value，另一方面我们还要有个 outer dictionary 来 map 每一层的位置和每一层的 leaf nodes。
简而言之，我们需要这样一个东西 Dictionary<int[], Dictionary<string, object>> ，输出的结果长这样。
Note：
- Queue，enqueue 和 dequeue 能保证我们不断地进入下一个 level，把每一个 level 的 token 都存进 queue，然后 dequeue 的时候假如是 value 就存入 dictHierarchy
- concat path 可以定义 connector，用来构造 json path（array 和 object 有区别）
- IntArrayEqualityComparer 是用来比较 dictionary key 的，key 是一个 int array，hashcode 用来 check object identity
- Tuple 可以用来 create value object
int[] a = new int[0];就是 create 一个 length = 0 的 int array，后面要用到qt.Item1.Append(arrIdx).ToArray()来赋值。
public class IntArrayEqualityComparer : IEqualityComparer<int[]>
{
public bool Equals(int[] x, int[] y)
{
if (x.Length != y.Length)
{
return false;
}
for (int i = 0; i < x.Length; i++)
{
if (x[i] != y[i])
{
return false;
}
}
return true;
}
public int GetHashCode(int[] obj)
{
int result = 17;
for (int i = 0; i < obj.Length; i++)
{
unchecked
{
result = result * 23 + obj[i];
}
}
return result;
}
}
public static string ConcatePath(string prefix, string name, string connector)
{
return (string.IsNullOrEmpty(prefix) ? name : prefix + connector + name);
}
public static Dictionary<int[], Dictionary<string, object>> JtokenToDictionaryHierarchy(JToken startToken)
{
var dictionaryHierarchy = new Dictionary<int[], Dictionary<string, object>>(new IntArrayEqualityComparer());
var arrayCount = 0;
// Create the queue and add the starting element
var queue = new Queue<Tuple<int[], string, JToken>>();
queue.Enqueue(Tuple.Create(new int[0], string.Empty, startToken));
// Loop through the token
while (queue.Count > 0)
{
var qt = queue.Dequeue();
switch (qt.Item3.Type)
{
case JTokenType.Object:
foreach (JProperty prop in qt.Item3.Children<JProperty>())
{
queue.Enqueue(Tuple.Create(qt.Item1, ConcatePath(qt.Item2, prop.Name, "."), prop.Value));
}
break;
case JTokenType.Array:
int arrIdx = 0;
arrayCount++;
foreach (JToken value in qt.Item3.Children())
{
queue.Enqueue(Tuple.Create(qt.Item1.Append(arrIdx).ToArray(), ConcatePath(qt.Item2, $"[]", ""), value));
arrIdx++;
}
break;
default:
if (!dictionaryHierarchy.ContainsKey(qt.Item1))
dictionaryHierarchy.Add(qt.Item1, new Dictionary<string, object>());
dictionaryHierarchy[qt.Item1].Add(qt.Item2, ((JValue)qt.Item3).Value);
break;
}
}
return dictionaryHierarchy;
}
Step 3：Flatten Record Related Values
第三步，当我们给定一个 match path 和 match value 时（给出 match 条件），需要返回一个包含所有与 match value 相关的 dictionary，这样我们才能用这个 result 去搜索我们最终希望得到的 value（和 match 条件不同的那个 path）。
Note：假如我们想支持 multiple match，只要稍加改动 GetFirstMatchAsRecord 这个 function 即可。
public static Dictionary<string, object> BuildRecord(Dictionary<int[], Dictionary<string, object>> dictHierarchy, int[] key)
{
var dictionaries = new List<Dictionary<string, object>>();
int[] keyIter = key;
while (keyIter.Length > 0)
{
if (dictHierarchy.TryGetValue(keyIter, out Dictionary<string, object> d))
dictionaries.Add(d);
// go to parent level
keyIter = keyIter.Take(keyIter.Length - 1).ToArray();
}
// convert dictionary list to dictionary
return dictionaries
.SelectMany(dict => dict)
.ToDictionary(pair => pair.Key, pair => pair.Value);
}
// we can return a list of dictionaries if we want to support multiple matches
public static Dictionary<string, object> GetFirstMatchAsRecord(string matchPath, string matchValue, Dictionary<int[], Dictionary<string, object>> dictHierarchy)
{
foreach (var kvp in dictHierarchy)
{
if (kvp.Value.ContainsKey(matchPath))
{
if (matchValue.Equals(kvp.Value[matchPath]?.ToString()))
return BuildRecord(dictHierarchy, kvp.Key);
}
}
return null;
}
Step 4：get the final value!
最后其实就很简单了，我们只要用 result dictionary + path 作为 key，就可以获取 value。
void Main()
{
JToken token = JToken.Parse(jsonString);
var dictHierarchy = JtokenToDictionaryHierarchy(token);
var result = GetFirstMatchAsRecord("[].employees[].positions[].title", "business analyst", dictHierarchy);
var employeeFirstName = result["[].employees[].values.first_name"];
employeeFirstName.Dump();
result.Dump();
dictHierarchy.Dump();
}
5. 完整代码
static string jsonString = @"
[
{
""employees"": [
{
""id"": 1,
""values"": {
""first_name"": ""Luna"",
""last_name"": ""Wen""
},
""positions"": [
{
""title"": ""developer""
}
]
},
{
""id"": 2,
""values"": {
""first_name"": ""Luna2"",
""last_name"": ""Wen2""
},
""positions"": [
{
""title"": ""business analyst""
}
]
},
{
""id"": 3,
""values"": {
""first_name"": ""Luna3"",
""last_name"": ""Wen3""
},
""positions"": [
{
""title"": ""tester""
}
]
}
],
""update_datetime"": ""2020-08-14T13:52:18+10:00""
}
]";
public class IntArrayEqualityComparer : IEqualityComparer<int[]>
{
public bool Equals(int[] x, int[] y)
{
if (x.Length != y.Length)
{
return false;
}
for (int i = 0; i < x.Length; i++)
{
if (x[i] != y[i])
{
return false;
}
}
return true;
}
public int GetHashCode(int[] obj)
{
int result = 17;
for (int i = 0; i < obj.Length; i++)
{
unchecked
{
result = result * 23 + obj[i];
}
}
return result;
}
}
public static string ConcatePath(string prefix, string name, string connector)
{
return (string.IsNullOrEmpty(prefix) ? name : prefix + connector + name);
}
public static Dictionary<int[], Dictionary<string, object>> JtokenToDictionaryHierarchy(JToken startToken)
{
var dictionaryHierarchy = new Dictionary<int[], Dictionary<string, object>>(new IntArrayEqualityComparer());
var arrayCount = 0;
// Create the queue and add the starting element
var queue = new Queue<Tuple<int[], string, JToken>>();
queue.Enqueue(Tuple.Create(new int[0], string.Empty, startToken));
// Loop through the token
while (queue.Count > 0)
{
var qt = queue.Dequeue();
switch (qt.Item3.Type)
{
case JTokenType.Object:
foreach (JProperty prop in qt.Item3.Children<JProperty>())
{
queue.Enqueue(Tuple.Create(qt.Item1, ConcatePath(qt.Item2, prop.Name, "."), prop.Value));
}
break;
case JTokenType.Array:
int arrIdx = 0;
arrayCount++;
foreach (JToken value in qt.Item3.Children())
{
queue.Enqueue(Tuple.Create(qt.Item1.Append(arrIdx).ToArray(), ConcatePath(qt.Item2, $"[]", ""), value));
arrIdx++;
}
break;
default:
if (!dictionaryHierarchy.ContainsKey(qt.Item1))
dictionaryHierarchy.Add(qt.Item1, new Dictionary<string, object>());
dictionaryHierarchy[qt.Item1].Add(qt.Item2, ((JValue)qt.Item3).Value);
break;
}
}
return dictionaryHierarchy;
}
public static Dictionary<string, object> BuildRecord(Dictionary<int[], Dictionary<string, object>> dictHierarchy, int[] key)
{
var dictionaries = new List<Dictionary<string, object>>();
int[] keyIter = key;
while (keyIter.Length > 0)
{
if (dictHierarchy.TryGetValue(keyIter, out Dictionary<string, object> d))
dictionaries.Add(d);
// go to parent level
keyIter = keyIter.Take(keyIter.Length - 1).ToArray();
}
// convert dictionary list to dictionary
return dictionaries
.SelectMany(dict => dict)
.ToDictionary(pair => pair.Key, pair => pair.Value);
}
// we can return a list of dictionaries if we want to support multiple matches
public static Dictionary<string, object> GetFirstMatchAsRecord(string matchPath, string matchValue, Dictionary<int[], Dictionary<string, object>> dictHierarchy)
{
foreach (var kvp in dictHierarchy)
{
if (kvp.Value.ContainsKey(matchPath))
{
if (matchValue.Equals(kvp.Value[matchPath]?.ToString()))
return BuildRecord(dictHierarchy, kvp.Key);
}
}
return null;
}
void Main()
{
JToken token = JToken.Parse(jsonString);
var dictHierarchy = JtokenToDictionaryHierarchy(token);
var result = GetFirstMatchAsRecord("[].employees[].positions[].title", "business analyst", dictHierarchy);
var employeeFirstName = result["[].employees[].values.first_name"];
employeeFirstName.Dump();
result.Dump();
dictHierarchy.Dump();
}
6. 结语
这个功能当时真的困扰了我好久好久，可能还是抽象思维不够，以及很少做这种数据结构相关的训练。
最后，源代码来自同事，并不是我自己写的，这篇文章的目的是解析这段代码，学习同事的思维，下次遇到类似的问题可以举一反三。