我已经研究这个算法好几天了，不知道如何找出最合适/最简单/优化的解决方案。
在这里，我有大量的字符串数组，如下所示
[
*.*.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
所有值都采用一些通配符模式(实际上，它们是我系统的权限)
我想做的是删除冗余模式，例如：由于*.*.read，admin.json_api.read是多余的
有人可以给我任何建议/方法吗？
以下方法还考虑了不同的球段长度。
因此，在第一步中，球形阵列被简化为一个或多个段长度的更好可检查球体项目的特定阵列。
例如，此类项目具有其实际 glob 值的正则表达式特定模式。
在最终任务中，每个段长度的特定数组都会被单独清理为一个非冗余 glob 值数组。
后者通过1st对每个数组进行降序按每个项目的 glob 值降序来实现(这确保了从更通用的 glob 值到不太通用的 glob 值的排序)，第二个通过拒绝每个项目来实现，其中 glob 值已经被更通用的 glob 值覆盖。
这种检测的基础是全球值特定的正则表达式，其中星号通配符转换为具有相同含义的正则表达式模式......因此，任何 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; }一般思路：
- 您的每个模式都可以使用以下方法转换为正则表达式：
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);