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

You can nearly directly translate this into scala code.

Idiomatically, you would use Animal, Cat, Dog - with uppercase in scala, but to match your example, I leave the road of convention here:

abstract sealed class animal () {}
 object cat extends animal () {}
 object dog extends animal {}

abstract sealed class color () {}
 object white extends color {}
 object black extends color {}
 object gray  extends color {}

abstract sealed case class gender () {}
 object male   extends gender {}
 object female extends gender {}

def input (a: Option[animal], c: Option[color], g: Option[gender]) = (a, c, g) match {
  case (Some (dog), Some (gray), Some (male)) => println ("y called without freedom")
  case (_,          Some (gray), Some (male)) => println ("x called with animal" + a)
  case (_,          _,           _          ) => println ("z called with anmimal: " + a + "\tcolor: " + c + "\tgender: " + g)
}

input (Some (dog), Some (gray), Some (male))
input (None,       Some (gray), Some (female))

Result:

y called without freedom
x called with animal: None

You have to take care on the sorting in the 'input'-Method. Specific methods have to come before unspecific ones.

And there are some cases, where, from your description it is undecideable what to do, but you have to decide, which test comes first:

(a, c, _)
(_, c, g)
(a, _, g) 

do all have 1 open case. If there is nothing else, (a, c, g) could match any of them, but will only match the first one.

You have to provide a general case (_, _, _), but may throw an error, if it doesn't make sense.

Answer 3

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
   

Answer 4

I would first give all variables a unique value (array position)

Animal: any = 0; cat = 1; dog = 2
Gender: any = 0; male = 1; female = 2
Color : any = 0; white = 1; black = 2; gray = 3;

Then I would give each possible combination is given a lookup value.

             Animal-|        ANY        |       cat         |       dog         |       
                    ------------------------------------------------------------- 
             Gender-| any | male |female| any | male |female| any | male |female| 
                    ============================================================= 
      Color-any     |  0  |   1  |   2  |  3  |   4  |   5  |  6  |   7  |   8  |
                    ------------------------------------------------------------- 
            white   |  9  |  10  |  11  | 12  |  13  |  14  | 15  |  16  |  17  |
                    ------------------------------------------------------------- 
            black   | 18  |  19  |  20  | 21  |  22  |  23  | 24  |  25  |  26  |   
                    ------------------------------------------------------------- 
            gray    | 27  |  28  |  29  | 30  |  32  |  33  | 34  |  35  |  36  |
                    =============================================================

Each lookup value can be calculated by the following:

(Animal * number of animals) + Gender + (Color * number of animals * number of sexes)

or in the case of: animal is any, (0) color is gray, (3) gender is male, (1)

(Animal * number of animals) + Sex + (Color * number of animals * number of sexes)
(   0   *        3         ) +  1  + (  3   *        3          *        3       )  

(0 * 3) + 1 + (3 * 3 * 3)  
   0    + 1 +      27       = 28 (the lookup value from the grid above)

28 means call X.

So in your program:

Calculate you value Compare that value against known cases

if Value in (1,2,8,13,14,15,21,28)    then X
if value in (3,4,5,23,24,26,34,35,36) then Y
if value in (0,9,12,16,17,22,25)      then Z

Obviously those value could actually be stored in a config file so you could change the logic without a re-compile.

Answer 5

The right answer depends on how fancy you want to get. There are things like the Rete algorithm. Google "expert systems". I've worked in big corporations that have rule evaluation systems, but they don't write them in-house-- they buy a commercial package.

If your needs are simple, then a search tree where each level is a category would work. If the application only has specific items and one general "any" item, this would work fine. If there are multiple levels of generality ("mammal", "vertebrate", "animal") it gets tougher.

If speed is an issue, but memory usage is not, then you could also try the hashtables-of-hashtables approach. Each entry in a hashtable is a key-value pair. In the top-level hashtable, the key is the top category: "dog", "cat", "any". The value is another hashtable. In the second-level hashtable, the key is the color and the value is a another hashtable. And so on. The value of the deepest hashtable contains a function pointer, closure, or whatever method of dynamic invocation your programming languages offers.