RegExp comme bibliothèque pour motif matriciel recherche

Question

Y at-il une bibliothèque (dans toutes les langues) qui peuvent rechercher des modèles dans les expressions régulières comme matrices de travail pour les chaînes? Quelque chose comme pour des expressions régulières, ou toute matrices méthode de recherche de motif matriciel?

Answer 1

Si vous n'êtes pas opposé à l'aide de J, vous pouvez savoir si deux matrices sont égales en utilisant l'opérateur de -: (match). Par exemple:

   X =: 4 3 $ i.12
   X
0  1  2
3  4  5
6  7  8
9 10 11
   Y =: 4 3 $ (1+i.12)
   Y
 1  2  3
 4  5  6
 7  8  9
10 11 12
   X -: X
1
   X -: Y
0

Une fonctionnalité de l'opérateur de correspondance est que vous pouvez l'utiliser pour comparer les tableaux de dimension arbitraire; si A est une matrice 3x3x4 et B est une matrice de 2x1, ensuite les rendements A-:B 0.

Pour savoir si une matrice est une sous-matrice d'une autre matrice, vous pouvez utiliser l'opérateur E: (membre de l'intervalle) comme ceci:

 X =: 2 2 $ 1 2 4 5  
   X
1 2
4 5
   Y =: 4 3 $ (1+i.12)
   Y
 1  2  3
 4  5  6
 7  8  9
10 11 12
   X E. Y
1 0 0
0 0 0
0 0 0
0 0 0

1 dans la partie supérieure gauche du résultat signifie que la partie de Y qui est égale à X a le pixel donné en tant que son coin supérieur gauche. La raison pour cela est qu'il peut y avoir plusieurs copies de X qui se chevauchent intégrés dans Y, et seul le repérage d'un pixel vous permet de voir l'emplacement de chaque tuile correspondant.

Answer 2

J'ai trouvé deux choses: gawk et perl script.

Il est un autre problème parce que la chaîne travail régulier expressions (par exemple, sed, grep) ligne par ligne travail sur les chaînes unidimensionnelles.

À moins que vos matrices sont unidimensionnels (essentiellement des vecteurs), ces programmes et les algorithmes qu'ils utilisent ne fonctionnera pas.

Bonne chance!

Answer 3

Il suffit de chercher des rangées de motif dans chaque rangée de la matrice d'entrée en utilisant Aho-Corasick (temps O (taille de la matrice)). Le résultat devrait être assez petit pour rejoindre rapidement dans le résultat final.

Answer 4

Je ne pense pas qu'il existe quelque chose de semblable expressions régulières pour des dimensions supérieures à 1, mais si vous voulez faire correspondre un modèle exact au lieu d'une classe de modèles alors je pourrais vous suggère de lire sur convolution (ou plutôt corrélation croisée)

La raison étant, il existe de nombreuses fonctions bibliothèque hautement optimisées (par exemple. IPP) pour faire cela plus vite que vous ne pourriez jamais espérer réaliser sur votre propre. De plus, cette méthode des échelles de dimensions supérieures aussi bien.

En outre, cela vous donnera pas nécessairement un « match », mais plutôt un « pic » dans une carte de corrélation qui correspondra au match si ce pic est égale à la somme des coefficients au carré du modèle que vous recherchez pour.