Rules matching given an input (algorithm)

Question

Let's suppose I have the following categories (with their possible values):

animal: any, cat, dog
color: any, white, black, gray
gender: any, male, female
[...]

or more generally...

category: <array of values>

(1) Let's say I have a set of configurable rules like:

when animal is any, color is gray, gender is male, call x
when animal is dog, color is gray, gender is male, call y
when animal is any, color is any, gender is any, call z
[...]

(2) And some input values.

Q. Is there an algorithm that solves the problem of finding a matching rule (with a priority given to the most specific rule found) according to the input given?

Ex.1:

input (animal:dog, color:gray, gender:male)

it would call "y"

Ex.2:

input (color:gray, gender:female)

it would call "z"

Is the more appropriate way to do it is building a search tree based on the rules (each level of the tree being a category)?

like:

- any animal
  - any color
    - any gender => z
  - gray
     - male => x
- dog
  - gray
     - male => y

Is there a better way of doing it?

Thanks!

Answer 1

I would hash the rules into a map and then look up with same hash.

map[hash(animal, color, gender)] = function to call

call map[hash(inputanimal, inputcolor, inputgender)]

This would ensure faster creation of rules and resolution of the correct function to call based on input.

If the rule must be matched exactly or else fall to the generic any,any,any then it is simply done by:

if map.contains(hash(inAnimal, inColour, inGender)) 
   x = map[hash(inAnimal, inColour, inGender)]
else
   x = map[hash(any, any, any)]

Otherwise if it starts with the input and successively selects the any rule on each parameter then you could do this.

Have the hash function accept an array of values. When you try to match a rule, you start with the input, and then successively switch each to any, until you find a match.

def key hash(array[])

....

resolution process...

input[] = {inAnimal, inColour, inGender}
function x
for(i = 0 to input.size) {
   if(map.contains(hash(input)) {
      x = map[hash(input)]
      break
   }
   input[i] = any
}
call x

Answer 2

A decision tree with following modifications would work:

1. Create the decision tree in normal way with 'any' as edges using all the rules

2. While traversing recursively, traverse to both 'value' and 'any' and keep track of number 'any's in each solution, return the one with minimum 'any's

   def traverse(values, level, tree,anyCount): If tree is is a leaf: return (appr_func, anyCount)

   v1 = None
   if values[level] in tree:
       v1 = traverse(values, level+1, tree[values[level]]], anyCount)
   
   v2 = None
   if 'any' in tree:
       v2 = traverse(values, level+1, tree['any'], anyCount+1)
   
   if v1!=None:
       if v2!=None:
           if v1[1]<v2[1]:
               return v1
           else:
               return v2
       else:
           return v1
   elif v2!=None:
       return v2
   else:
       return None