Problems found in new sorting algorithm

[kirsle]

In #67 the sorting algorithm was refactored and I found a rather visible breakage from it: in the example bot I wasn't able to match the hello triggers:

You> hello bot
Bot> Please go on.
You> hi
Bot> I'm not sure I understand you fully.
You> my name is noah
Bot> Noah, nice to meet you.
You> hello
Bot> Please go on.

In the previous state of the master branch (commit 405e391) it gives the expected result:

You> hello bot
Bot> Hi. What seems to be your problem?
You> hello
Bot> How do you do. Please state your problem.

I made this local change to my rivescript/interactive.py to print the sorted lists for both versions:

diff --git a/rivescript/interactive.py b/rivescript/interactive.py
index 3b67727..5cf9510 100644
--- a/rivescript/interactive.py
+++ b/rivescript/interactive.py
@@ -200,6 +200,12 @@ def interactive_mode():
     bot.load_directory(args.path)
     bot.sort_replies()
 
+    topics = sorted(bot._sorted['topics'].keys())
+    for topic in topics:
+        print("Topic:", topic)
+        for trigger in bot._sorted['topics'][topic]:
+            print("\t", trigger[0])
+
     # Interactive mode?
     if args.json:
         # Read from standard input.

I've attached the outputs of the above sort lists:
broken-sort.txt
good-sort.txt

Here is a snippet of the buggy version's output around the relevant trigger:

  	 i am *
  	 everyone *
- 	 *
  	 i am (sad|unhappy|mad|angry|pissed|depressed) [*]
  	 i am (happy|excited|glad) [*]
+ 	 (hello|hi|hey|howdy|hola|hai|yo) [*]
  	 (what|who|when|where|how) [*]
  	 my (girlfriend|boyfriend)* name is *

So it seems the bare wildcard * took a higher precedence over triggers that contained alternatives and optional *'s.

I also saw similar cases in the output of the triggers not being sorted the best: in the topics used for the RPG game demo, the _ * trigger was at the very bottom (below *) when they should've been in the opposite order (_ * > *).

---

I'm not planning a new official release too soon, so I'll leave PR #67 merged for now and hopefully these last couple bugs can be resolved. If I do need to make a new release before then I'll have to revert #67 and try again later.

[htdinh]

Indeed, I realise that we missed out the attribute for alternatives (a|b). I am even more surprised to check on Try RiveScript Online that alternatives is allowed within the optional brackets, such that literally [a|b]=(a|b|) where the third option is just nothing or absence of any option. Of course, the (a|b|) does not pass the current RiveScript syntax check, but I put that way to illustrate the point and you may consider for possible update. My surprise is probably because you didn't make it clear in the trigger documentation that alternatives signature | is allowed inside optional brackets [], a stronger example would be what is your [home|cell] phone number?. This matches exactly 3 cases when replacing the brackets by either home,cell, or nothing.

Of course this usage allows flexibility from the perspective of language. But are you afraid that it may cause confusion as well?

As you have grouped alternatives under the name of optionals, in brain.py where RE.optionals = re.compile(r'\[(.+?)\]'), this leads to the ambiguity of optionals when sorting is required. Optionals could mean alternatives (parentheses) or non-alternative (square bracket). I may need to add another additional RE.alternatives to make clear whether alternatives present.

[htdinh]

It will simplify the sorting problem if we don't take into account the number of special signature i.e. _ in the template. But I think including that will be a small extension if we have a working sorting method. So I need a more precise definition of sorting rule. Assuming descending order of priority, do you agree on the following order?

atomic > _ > _ _ > _ * > _ _ * > *

[kirsle]

Optionals vs. Alternatives

Alternatives:

• Alternatives are surrounded by parenthesis, like what is your (home|cell) phone number
• At least one of the parts of the alternative must be in the user's message for matching to occur
• The captured value from the message goes into a <star> tag.

Optionals:

• Optionals are surrounded by square brackets, like what is your [home|cell] phone number
• At least one part of the optional, or none of them at all, must be in the user's message for matching to occur.
  • Example: what is your home phone number matches
  • Example: what is your phone number matches
  • Example: what is your office phone number does not match
• The captured value of the optional does not go into a <star> tag.

Under the hood these features are very similar: in the alternative form, the regular expression looks exactly the same as the source, like:

/^what is your (home|cell) phone number$/

Edit/Clarification: about the use of RE.optionals in reply_regexp: the only special case with the regexp engine for RiveScript is how the optionals work, as the normal alternatives are literally just standard regular expression syntax already. So the reply_regexp doesn't have its own block of code for doing anything with normal alternatives, only for the optionals.

For optionals, the regular expression adds a bunch of extra metacharacters to make sure that it doesn't get captured into a <star> tag (by surrounding it with (?:...), where the ?: makes it non-capturing), and additional characters are inserted to detect word boundaries and whitespace to make it possible that the user's message does not contain any of the parts of the optional at all (by putting the sequence (?:\s|\b)+ on either side of each part, as well as including a new part that consists only of (?:\s|\b) to catch the word not being in the message at all).

/^what is your(?:(?:\s|\b)+home(?:\s|\b)+|(?:\s|\b)+cell(?:\s|\b)+|(?:\s|\b))phone number$/

The documentation should probably be updated to make it clearer that optionals can have alternatives inside them.

Sort Order for Wildcards

Assuming descending order of priority, do you agree on the following order?

atomic > _ > _ _ > _ * > _ _ * > *

Generally when you get down to just sorting the wildcard-only triggers, the order of priority for the types of wildcards goes _ > # > *, with the * at the end because it would also match the same things _ and # match.

The order of triggers you listed would match the following types of messages in this order:

1. Atomic triggers
2. The user said a single word
3. The user said two words (separated by a space)
4. The user said one word, and then one or more of anything
5. The user said two words, and then one or more of anything
6. Anything else the user said that wasn't matched.

Step 5 above would not be matched because step 4 would've also matched any messages that match on step 5. So I'd probably switch those around; but if this is difficult I wouldn't worry too much about it, as the tail end of the sort list has always been a sort of grey edge-case area anyway.

[kirsle]

Also, the optional [a|b] isn't strictly the same as what (a|b|) would be: if optionals used a simple regexp like that, the user would require hitting space twice when they don't want to include the optional.

Python 3.5.2 (default, Sep 14 2016, 11:28:32) 
[GCC 6.2.1 20160901 (Red Hat 6.2.1-1)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import re
>>> trigger = re.compile(r'^what is your (home|cell|) phone number$')
>>> trigger.match("what is your home phone number")
<_sre.SRE_Match object; span=(0, 30), match='what is your home phone number'>
>>> trigger.match("what is your cell phone number")
<_sre.SRE_Match object; span=(0, 30), match='what is your cell phone number'>
>>> trigger.match("what is your phone number")
>>> trigger.match("what is your  phone number")
<_sre.SRE_Match object; span=(0, 26), match='what is your  phone number'>
>>>

Slightly more accurately, [a|b] would be equivalent to (?:a|b|(?:\s|\b)), with the "empty" value being actually a whitespace or word boundary so that the input message doesn't need two spaces to match the missing optional.

[ekt1701]

I found an issue with the sorting of wildcards: * comes before [*]

I have a number of commands that start with [*], but now with the current update, my one catchall command + * is called before all of them.

[htdinh]

Yes, there is an issue with the combination of triggers coexist in the template (in our case, * and [] together making [*]). I will try to fix this issue.

[htdinh]

@kirsle How to print the sorted list as you proposed to change the interactive.py above? It seems that when I run the example.py, the print section is never reached.

At least how to see this print.

    print(
        "      .   .       \n"
        "     .:...::      RiveScript Interpreter (Python)\n"
        "    .::   ::.     Library Version: v{version}\n"
        " ..:;;. ' .;;:..  \n"
        "    .  '''  .     Type '/quit' to quit.\n"
        "     :;,:,;:      Type '/help' for more options.\n"
        "     :     :      \n"
        "\n"
        "Using the RiveScript bot found in: {path}\n"
        "Type a message to the bot and press Return to send it.\n"
        .format(version=bot.VERSION(), path=args.path)

[kirsle]

Run it like python shell.py eg/brain

[kirsle]

#69 seems to have adequately solved the sorting problem. When comparing it to the old algorithm it actually sorted some triggers better than it did before (the good-sort.txt had a few entries in the random topic that got sorted below the * trigger which shouldn't happen).