我已經研究這個演算法好幾天了，不知道如何找出最合適/簡單/優化的解決方案。
在這里，我有一個大的字串陣列，如下所示
[
*.*.complete
*.*.read
*.*.update
*.order.cancel
accounting.*.delete
accounting.*.update
accounting.*.void
accounting.account.*
admin.user.read
admin.user.update
admin.format.delete
...
]
// the array may be in random order
所有的值都在一些通配符模式中（實際上，它們是我系統的權限）
我想要做的是洗掉冗余模式，例如：admin.json_api.read是多余的，因為*.*.read
有人可以給我任何建議/方法嗎？
uj5u.com熱心網友回復：
以下方法也考慮了不同的全域段長度。
因此，在第一步中，glob-array 被簡化為一個或多個段長度特定的更好檢查的 glob-item 的陣列。
這樣的專案具有例如其實際全域值的正則運算式特定模式。
在最終任務中，每個段長度特定的陣列都被分別清理為一個非冗余全域值陣列。
后者是通過第一次按每個專案的 glob 值降序對每個陣列進行排序來實作的（這確保了從更多到不太通用的 glob 值的排序），第二個是通過拒絕其 glob 值已經被更通用的 glob 覆寫的每個專案-價值。
這種檢測的基礎是特定于 glob-value 的正則運算式，其中星號通配符轉換為具有相同含義的正則運算式模式......因此任何 glob 值'*.'等于 的正則運算式，/[^.] \./任何終止'.*'等于 的正則運算式/\.[^.] /。
由于清理任務是通過 完成的flatMap，最終結果又是一個平面陣列......
function createGlobInspectionItem(glob) {
const segments = glob.split('.');
return {
value: glob,
pattern: glob
.replace((/\*\./g), '[^.] .')
.replace((/\.\*$/), '.[^.] ')
.replace((/(?<!\^)\./g), '\\.'),
segmentCount: segments.length,
};
}
function collectGlobInspectionItems({ index, result }, glob) {
const globItem = createGlobInspectionItem(glob);
const groupKey = globItem.segmentCount;
let groupList = index[groupKey];
if (!groupList) {
groupList = index[groupKey] = [];
result.push(groupList);
}
groupList.push(globItem);
return { index, result };
}
function createSanitizedGlobList(globItemList) {
const result = [];
let globItem;
globItemList.sort(({ value: aValue }, { value: bValue }) =>
(aValue > bValue && -1) || (aValue < bValue && 1) || 0
);
while (globItem = globItemList.pop()) {
globItemList = globItemList.filter(({ value }) =>
!RegExp(globItem.pattern).test(value)
);
result.push(globItem);
}
return result.map(({ value }) => value);
}
const sampleData = [
// 3 segments
'*.*.complete',
'*.*.read',
'*.*.update',
'*.order.cancel',
'accounting.*.delete',
'accounting.*.update',
'accounting.*.void',
'accounting.account.user',
'accounting.account.*',
'accounting.account.admin',
'admin.user.read',
'admin.user.update',
'admin.format.delete',
// 2 segments
'*.read',
'*.update',
'user.read',
'user.update',
'format.delete',
'format.account',
];
console.log(
'... intermediata inspection result grouped by section length ...',
sampleData
.reduce(collectGlobInspectionItems, { index: {}, result: [] })
.result
);
console.log(
'... final sanitized and flattened glob array ...',
sampleData
.reduce(collectGlobInspectionItems, { index: {}, result: [] })
.result
.flatMap(createSanitizedGlobList)
);.as-console-wrapper { min-height: 100%!important; top: 0; }uj5u.com熱心網友回復：
大概的概念：
- 您的每個模式都可以使用以下方法轉換為正則運算式：
new RegExp('^' pattern
.replace(/[./]/g, '\\$&') // escape chars (list isn't full)
.replace(/\*/g, '(.*)') // replace asterisk with '(.*)' - any char(s)
'$') // match only full pattern
- 如果一種模式與另一種模式匹配 - 您不需要兩者，因為
*包含第二個模式的模式：
if (pattern1.include('*') && pattern1.test(pattern2)) {
// delete pattern2
}
簡單的實作可以在下面找到（還需要優化一下）。
完整代碼：
// Your initial array
const patterns = [
'*.*.complete',
'*.*.read',
'*.*.update',
'*.order.cancel',
'accounting.*.delete',
'accounting.*.update',
'accounting.*.void',
'accounting.account.*',
'admin.user.read',
'admin.user.update',
'admin.format.delete',
]
// Build a new one with regexes
const withRegexes = patterns.map(pattern => {
// Create a regex if pattern contain asterisk
const regexp = pattern.includes('*') ? new RegExp('^' pattern
.replace(/[./]/g, '\\$&')
.replace(/\*/g, '(.*)')
'$') : null;
return { pattern, regexp };
});
// Array of indexes of elements where it's pattern already matched by another pattern
let duplicateIndexes = [];
for (let i = 0; i < withRegexes.length - 1; i ) {
for (let j = i 1; j < withRegexes.length; j ) {
if (withRegexes[i].regexp
&& withRegexes[i].regexp.test(withRegexes[j].pattern)) {
duplicateIndexes.push(j);
}
}
}
// Get unique indexes to delete in desc order
duplicateIndexes = [ ...new Set(duplicateIndexes) ].sort((a, b) => b - a);
// Clear up initial array
for (let index of duplicateIndexes) {
patterns.splice(index, 1);
}
// New one
console.log(patterns);轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/420677.html
標籤：