He estado trabajando en este algoritmo durante días y no tengo idea de cómo encontrar la solución más adecuada/fácil/optimizada.
Aquí tengo una gran variedad de cadenas como las siguientes
[ *.*.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 ordertodos los valores están en algunos patrones comodín (de hecho, son los permisos para mi sistema)
lo que quiero hacer es eliminar patrones redundantes, por ejemplo: admin.json_api.read es redundante debido a *.*.read
¿alguien puede darme alguna sugerencia/enfoque?
Idea general:
new RegExp('^' + pattern .replace(/[./]/g, '\\$&') // escape chars (list isn't full) .replace(/\*/g, '(.*)') // replace asterisk with '(.*)' - any char(s) + '$') // match only full pattern* incluye el segundo: if (pattern1.include('*') && pattern1.test(pattern2)) { // delete pattern2 }La realización simple se puede encontrar a continuación (todavía es necesario optimizar un poco).
Código completo:
// 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);El siguiente enfoque también tiene en cuenta diferentes longitudes de segmentos globales.
Así, en un primer paso, la matriz global se reduce a una o más matrices específicas de longitud de segmento de elementos globales mejor inspeccionables.
Dicho elemento presenta, por ejemplo, un patrón específico de expresiones regulares de su valor global real.
Dentro de una tarea final, cada matriz específica de longitud de segmento se desinfecta por separado en una matriz de valores globales no redundantes.
Lo último se logra primero clasificando cada matriz descendiendo por el valor global de cada elemento (lo que asegura una clasificación de los valores globales más genéricos a los menos) y segundo rechazando cada elemento donde su valor global ya está cubierto por un valor global más genérico. -valor.
Y la base de dicha detección es la expresión regular específica del valor global donde el comodín de asterisco se traduce en un patrón de expresión regular con el mismo significado... por lo tanto, cualquier valor global de '*.' es igual a una expresión regular de /[^.]+\./ y cualquier terminación '.*' es igual a una expresión regular de /\.[^.]+/ .
Dado que la tarea de desinfección se realiza a través de flatMap , el resultado final es una matriz plana nuevamente...
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; }