Order of the match path components

[Helio Perroni Filho]

The AIML standard states [1] that "an AIML interpreter
must construct a match path from each category at
load-time", and that "a match path has three
components, whose order is mandatory": (pattern),
(that) and (topic).

My question is, what is the rationale behind this
ordering? To me it looks the inverse would be a more
efficient option. So long most categories have unset
(topic) and (that) sections (something that is
probably true for most AIML sets), a match path of the
form:

TOPIC ELEMENTS (TOPIC) THAT ELEMENTS (THAT) PATTERN
ELEMENTS

Would allow for more compact match graphs, since all
topic-less, that-less categories would be placed under
the same root node. Of course, this arrangement would
cause the repetition of equivalent pattern elements
from categories under different (topic) and/or (that)
sections; but so long the number of unique (topic,
that) pairs remained slow, this would be more than
compensated by the savings.

Am I missing something here?

[1]
http://www.alicebot.org/TR/2005/WD-aiml/#section-load-time-match-path-construction

--
Ja mata ne.
Helio Perroni Filho



       



       
               
_______________________________________________________
Yahoo! Acesso Grátis: Internet rápida e grátis.
Instale o discador agora!
http://br.acesso.yahoo.com/

_______________________________________________
alicebot-developer mailing list
alicebot-developer@...
http://list.alicebot.org/mailman/listinfo/alicebot-developer

[Dr. Rich Wallace]

Helio, I think there is no good reason except that's how the architecture
commmittee decided the standard, based on the existing early AIML
interpreters.  We've kept it that way for compatibility.  One idea that's
been discussed over the years is to generalize the <pattern,that,topic>
triple to a botmaster-defined infinite number of pattern-contexts, which
could include concepts such as bot name, mood, state, personality and so
on.  There is in principle no reason the botmaster should not be allowed
to redefine the order as well as the number of levels of matching.

Note that it isn't necessarily true that the graph has to take up a lot of
memory when the "topic" and "that" are both "*", because one could
compress these paths with a special terminal node.

> The AIML standard states [1] that "an AIML interpreter
> must construct a match path from each category at
> load-time", and that "a match path has three
> components, whose order is mandatory": (pattern),
> (that) and (topic).
>
> My question is, what is the rationale behind this
> ordering? To me it looks the inverse would be a more
> efficient option. So long most categories have unset
> (topic) and (that) sections (something that is
> probably true for most AIML sets), a match path of the
> form:
>
> TOPIC ELEMENTS (TOPIC) THAT ELEMENTS (THAT) PATTERN
> ELEMENTS
>
> Would allow for more compact match graphs, since all
> topic-less, that-less categories would be placed under
> the same root node. Of course, this arrangement would
> cause the repetition of equivalent pattern elements
> from categories under different (topic) and/or (that)
> sections; but so long the number of unique (topic,
> that) pairs remained slow, this would be more than
> compensated by the savings.
>
> Am I missing something here?
>
> [1]
> http://www.alicebot.org/TR/2005/WD-aiml/#section-load-time-match-path-construction
>
> --
> Ja mata ne.
> Helio Perroni Filho
>
>
>
>
>
>
>
>
>
> _______________________________________________________
> Yahoo! Acesso Grátis: Internet rápida e grátis.
> Instale o discador agora!
> http://br.acesso.yahoo.com/
>
> _______________________________________________
> alicebot-developer mailing list
> alicebot-developer@...
> http://list.alicebot.org/mailman/listinfo/alicebot-developer

--
Dr. Rich
W A L L A C E
ALICE A.I. Foundation
drwallace@...
Winner, Loebner Prize 2000, 2001, 2004


_______________________________________________
alicebot-developer mailing list
alicebot-developer@...
http://list.alicebot.org/mailman/listinfo/alicebot-developer

[Kim Sullivan]

> My question is, what is the rationale behind this
> ordering?

It's not storage efficiency or matching speed, it's matching behaviour. The
order is defined such that (basically) a more concrete pattern overrides a
more general pattern, but that given two equal patterns, the one with the
more concrete 'that' overrides the one with the less concrete that. If you
reverse the order, the semantics get changed too. The desired behaviour is a
lexicographic ordering of categories. Obviously, if you change the order in
which the elements are "compared", you change the resulting ordering, and
achieve different results e.g. you might sort a database first by name, and
then by score, or first by score and then by name. While the second approach
might be more efficient, it doesn't get you very far if you need an
alphabeticaly sorted list of names.

> To me it looks the inverse would be a more
> efficient option.

To attain matching efficiency, other routes have to be taken, for example,
not storing the "default" topic and 'that' (all those implied *). But, due
to the general set-up of the algorithm (and its desired behaviour), matching
will aways be exponential in the worst case.

Kim

_______________________________________________
alicebot-developer mailing list
alicebot-developer@...
http://list.alicebot.org/mailman/listinfo/alicebot-developer