用 E4X 和 Prototype 创建 Ajax mindreader 应用程序，第 1 部分: 构建 Twenty Questions 基础结构

成后的应用程序 E4X Mindreader 参见 参考资料。本系列假设您熟悉 XML 和 JavaScript 概念。如果需要了解背景知识，也请参见 参考资料。还需要一个支持 E4X 的浏览器，比如 Firefox 1.5 或更高版本。

在本系列中将开发的应用程序

常用缩写词 Ajax：Asynchronous JavaScript™ and XML DOM：Document Object Model HTML：Hypertext Markup Language JSON：JavaScript Object Notation XML：Extensible Markup Language

在本文中，将学习创建一个简单的 “Twenty Questions” 应用程序，它可以猜测用户心里想的东西，比如 “家猫” 或 “早餐麦片”。您可能认为猜测人的想法需要非常先进的应用程序。实际上，在 www.20q.net（参见 参考资料） 上可以找到一个先进的经过良好训练的神经网络。这个 www.20q.net 系统已经 “学习” 了 20 多年，可以接受多种有细微差别的回答 — 是、否、不知道、不相关、有时候、可能和不确定 — 并进行各种统计分析来解释它的数据库，最终的效果是它似乎能够读取用户的思想。

在本系列中，示例应用程序要简单得多。实际上，我们仅仅实现一个简单的二分查找法（binary search），这种算法的理论基础是：如果在一组可能的内容中不断删除不合适的内容，最终就会找到需要的东西。实际上，“twenty questions” 这个名字就来源于这样一种理论：对于包含宇宙中所有东西的集合，只需用大约 20 个不同的 “是/否” 问题进行排除，最终就可以找到一个东西。

在第 1 部分中，将构建一个自包含的系统，它从一个固定的知识库开始，然后向用户提问来判断用户心里想的东西。在第 2 部分中，将对系统进行培训，让它学习新东西。如果系统猜错了，系统会询问正确的东西以及如何从知识库中区分出它。然后，它把新知识添加到知识库中并重新开始。最后，将把这个功能与一个外部数据库集成起来，从而存储系统从所有用户那里学到的东西。

算法

说起来容易，但是究竟如何在浏览器中实现 Twenty Questions 呢？如果人与人之间玩这个游戏，提问人可以凭借经验决定下一个问题；计算机如何做出决定呢？

实际上很简单。二分查找算法 — 或更一般的分治算法 — 用每个问题排除大约一半儿的可能选择。例如，如果最初有 1024 个可能的选择，那么第一个问题把范围缩小到 512 个，第二个问题把范围缩小到 256 个，第三个问题把范围缩小到 128 个，以此类推。对于 1024 个可能的选择，只需要 10 个问题就可以找到目标。实际上，20 个问题可以区分 1,048,576 个不同的选择！

实际上，算法并不复杂。算法如下：

1. 装载知识库中的所有东西。
2. 询问用户他心里想的东西是 “动物、植物还是矿物？”
   应用程序使用的其他问题都要求回答是或否，但是这个问题是传统的 “第一个问题”，它可以排除大约 2/3 的可能选择。
3. 排除所有与这个问题的回答不相符的东西。
4. 如果范围已经收窄到一个东西，就询问用户这个猜测是否正确。
   如果正确，就重新装载知识库并重新开始游戏。如果不正确，就询问用户究竟是什么东西，并要求用户提供一个可以区分正确答案和错误答案的问题。将这些信息添加到知识库中。（将在第 2 部分中完成这一步骤。）
5. 如果仍然有多个东西，就要决定一个问题，这个问题应该应用于当前范围中尽可能多的东西。（这是关键；这样可以排除尽可能多的可能选择。）
6. 提出这个问题。
7. 返回到第 3 步。

E4X 非常适合实现这种算法。

注意：糟糕的是，无法强制用户向知识库中添加正确的信息，而提供错误信息的用户实际上使他们的内容无从查找。

E4X 简介

在编程环境中考虑处理 XML 时，您首先会想到什么？DOM？XPath？您首先想到的也许是 “哎唷，这真让人头疼！” 是的，确实是这样；XML 是一种出色的数据存储格式，但是处理 XML 却让人很头疼。但是，如果能够创建 XML 对象，轻松地访问和过滤 XML 节点，轻松地把数据序列化成显示或存储所需的字符串，那么会怎么样呢？您就不那么头疼了吧？

这就是 E4X 的价值所在。

E4X 使用一种与数据绑定相似的结构，简化了对 XML 文档的访问方法。请考虑下面这个片段（见清单 1）。

清单 1. 使用 E4X

<scripttype="text/javascript;e4x=1">

myquestion=<question>
<display>Isitanimal,vegetable,ormineral?</display>
<answerOption>Animal</answerOption>
<answerOption>Vegetable</answerOption>
<answerOption>Mineral</answerOption>
</question>;

alert("Thequestionis'"+myquestion.display+"'");

</script>

注意：请注意这个脚本的类型声明。在类型的末尾添加了 ";e4x=1"，这是为了关闭以前的 Mozilla E4X 实现中的某些向后兼容特性。

首先注意这并不是一个输入错误；在声明的 XML 周围没有引号。只需把 XML 直接放在代码中，这很方便。（另外，也可以从字符串创建对象。）还要注意，可以使用简单的对象语法获取 display 元素的值，这会产生图 1 所示的结果。

图 1. 显示 XML 中的信息

实际上，对于非文本数据，获取信息也很简单。请考虑清单 2。

清单 2. 显示原始数据

                
...
          </question>;

alert("The question is /n" + myquestion);   

这里引用整个 XML 文档，这会产生图 2 所示的结果。

图 2. 显示整个文档

很容易，不是吗？没有古怪的序列化函数或转换，只需把数据放在需要它的地方。

E4X 提供两个基本类：XML()（它相当于一个文档或一个元素）和 XMLList()（它相当于一个 Nodelist）。在本文中，您会看到它们的作用。

现在，开始构建应用程序。

创建知识库

第一步是创建一个实际的知识库。为此，需要一个简单的 XML 文档，其中包含要问的问题和它们针对的目标，见清单 3。

清单 3. 创建知识库

kdata=
<knowledgebase>
<questions>
<questionid="1">
<display>Isitanimal,vegetable,ormineral?</display>
<answerOption>Animal</answerOption>
<answerOption>Vegetable</answerOption>
<answerOption>Mineral</answerOption>
</question>
<questionid="2">
<display>Doesitbark?</display>
<answerOption>Yes</answerOption>
<answerOption>No</answerOption>
</question>
</questions>
<targets>
<targetid="1">
<display>ahousecat</display>
<answerquestionid="1"><answerValue1>Animal</
answerValue1></answer>
<answerquestionid="2"><answerValue2>No</
answerValue2></answer>
</target>
<targetid="4">
<display>adog</display>
<answerquestionid="1"><answerValue1>Animal</
answerValue1></answer>
<answerquestionid="2"><answerValue2>Yes</
answerValue2></answer>
</target>
<targetid="2">
<display>acarrot</display>
<answerquestionid="1"><answerValue1>Vegetable</
answerValue1></answer>
</target>
<targetid="3">
<display>aruby</display>
<answerquestionid="1"><answerValue1>Mineral</
answerValue1></answer>
</target>
</targets>
</knowledgebase>;

knowledgeBase=newXML(kdata);

在继续开发之前，先仔细看看这个结构，因为它包含算法的关键。首先，这个文档包含问题和目标。问题很简单；每个问题包含实际的问题和可能的答案。除了第一个问题之外，其他所有问题的答案只有 “yes” 和 “no”。这个结构允许以后添加可能的答案。

目标包含一个目标标识符（id）、目标的显示名以及系统知道的每个问题的答案。例如，它知道狗是一种动物而且狗会吠叫，而对于胡萝卜，它只知道胡萝卜是植物。当然，知道这么多就够了；因为植物是不会吠叫的！

在系统学习新的问题和答案时，会在现有的目标中添加它们。

提示：如果需要更智能化的知识库，可以从 http://backstop.nicholaschase.com/knowledgebase.php?getkb=YES 下载当前的知识库。

显示问题

下一步是提出第一个问题。为此，需要显示它。一种简便方法是创建一个可定制的 HTML，见清单 4。

清单 4. 问题表单

<html>
<head>
<title>E4Xmindreader</title>
<scripttype="text/javascript;e4x=1"src="e4x.js"></script>
<styletype="text/css">...
.answerLink{...}{color:blue;text-decoration:underline}
</style>
</head>
<bodystyle="background-color:#abdfe7;"onload="ask_question()">

<divid="questionFormDiv"
style="position:absolute;top:50px;visibility:hidden;width:100%;">

<spanid="displayQuestion"></span><br/>

</div>

</body>
</html>

这里有一个可以打开和关闭的 div（最初是关闭 的），其中有一个用来插入文本的 span。为了插入文本，需要能够选择一个特定的 XML 元素。

过滤节点

通过 E4X，可以用过滤器选择一个或多个节点，见清单 5。

清单 5. 使用过滤器

...
knowledgeBase=newXML(kdata);

varcurrentQuestion=1;


//******************************
//BEGINFUNCTIONSHERE
//******************************
functionask_question()...{

varquestionElement=knowledgeBase.questions.question.(@id==currentQuestion)

varquestionDisplay=questionElement.display;
document.getElementById("displayQuestion").innerHTML=questionDisplay;

show_form("questionFormDiv");

}

functionhide_form(divName)...{
document.getElementById(divName).style.visibility="hidden";
}
functionshow_form(divName)...{
document.getElementById(divName).style.visibility="visible";
}

在装载 HTML 页面时，它调用 answer_question() 函数，这会创建第一个问题。第一步是创建一个变量 questionElement，它保存代表第一个问题的 XML。（因为需要知道当前的问题，所以这个变量应该是全局变量。尽管这不是理想的编程实践，但是这并不是一个生产应用程序。）

请注意 ask_question() 开头的语法。它很像 XPath 谓词，而且工作方式也是一样的。在这个示例中，选择知识库，移动到根元素的 questions 子元素，然后找到 questions 元素的所有 question 子元素。然后，过滤掉所有与过滤器不相符的 question 元素 — 换句话说，只留下您需要的问题。

结果是一个单一元素，然后可以轻松地取出这个元素的 display 子元素，并用标准的 DOM 操作在页面上显示它，见图 3。

图 3. 显示问题

现在需要添加可能的答案。

处理 XMLList

可以用不同的方式允许用户在页面上输入信息。在这个示例中，使用 span 模拟链接，见清单 6。

清单 6. 答案

<spanid="displayQuestion"></span><br/>
<spanclass="answerLink"
onclick="answer_question(this)"id="answer1Text"></span>
<spanclass="answerLink"
onclick="answer_question(this)"id="answer2Text"></span>
<spanclass="answerLink"
onclick="answer_question(this)"id="answer3Text"></span>

这些链接引用 answer_question() 函数（稍后编写这个函数）。但是，首先需要填充答案，见清单 7。

清单 7. 填充答案

...
document.getElementById("displayQuestion").innerHTML=questionDisplay;

varanswerOptions=newXMLList();
answerOptions=questionElement.answerOption;

varanswerCounter=0;
document.getElementById("answer3Text").innerHTML="";
foreach(varanswerTextinanswerOptions)...{
answerCounter++;
document.getElementById("answer"+answerCounter+"Text").innerHTML=
answerText;
}
}
...

answerOptions 变量包含一个 XMLList，它与 DOM Nodelist 相似。在这个示例中，它包含当前 questionElement 中的所有 answerOption 元素。然后，可以在一个 for each 循环中使用这个列表，引用每个元素并把它添加到适当的 span 中。（首先清除第三个 span，因为在显示第一个问题之后，就不再使用它了。）

在完成的页面上，对于每个 answerOption 元素有一个链接，见图 4。

图 4. 第一个问题

那么，当用户回答这个问题时，会发生什么？

回答问题

当用户回答问题时，需要过滤掉与问题的答案不相符的所有东西。首先，需要获得当前要考虑的一组目标，见清单 8。

清单 8. 获得当前目标

...
varcurrentQuestion=1;
varcurrentTargetSet=knowledgeBase.targets;

//******************************
//BEGINFUNCTIONSHERE
//******************************
functionask_question()...{
...
}

functionanswer_question(answerSpan)...{
hide_form("questionFormDiv");

vartheAnswer=answerSpan.innerHTML;
varremainingTargets=
currentTargetSet..target.(answer["answerValue"+currentQuestion]==theAnswer);

alert("Thereare"+remainingTargets.length()+"targetsremaining: "+
remainingTargets);

}
...

注意，在这个清单的顶部，创建了一个新对象 currentTargetSet，它最初包含整个 targets 元素。但是，在 answer_question() 中，将删减其中的内容。

获得用户给出的答案之后（注意，这个函数的参数是实际的 span），可以对 currentTargetSet 进行过滤，创建一个新的 XMLList remainingTargets。

注意，这个表达式中使用了两个连续的点号。XPath 使用双斜线（//）表示后代，而 E4X 使用两个连续的点号（..）。在这里，首先获得根元素的所有 target 子元素，然后对它们进行过滤。

我们来仔细看看这个过滤器。在看到方括号时，您可能会想到 XPath 谓词，但这并不是 XPath 谓词。实际上，answer 变量是散列。这种方式与从 JavaScript 引用表单元素的传统方式相似，表达式 answer["answerValue1"] 相当于 answer.answerValue1。

这种形式的优点是，可以动态地指定要搜索的元素。在这个示例中，过滤器寻找 target 元素的条件是，元素的 answer.answerValue1 后代元素的值与用户给出的答案匹配。

与前面一样，过滤过程会产生一个 XMLList，然后可以检查这个列表的长度，从而判断目前还留下多少个目标。例如，如果用户选择 “Animal”，那么会留下两个目标，见图 5。

图 5. 留下两个目标

留下两个目标之后，需要找出下一个要问的问题，从而区分这两个目标。

选择下一个要问的问题

根据算法，下一个问题应该是与剩余目标最相关的问题，所以必须做一个假设。在生产系统中，可能会存储问过的每个问题，或者以其他方式确保排除以前问过的问题。在这个示例中，假设随着时间的推移以及知识库包含更多东西，问题的针对性会越来越强。我假设在游戏进行过程中，questionid 值逐渐增大，这样就很容易排除已经问过的问题，见清单 9。

清单 9. 排除已经问过的问题

...
varremainingTargets=
currentTargetSet..target.(answer["answerValue"+currentQuestion]==theAnswer);
alert("Thereare"+remainingTargets.length()+"targetsremaining: "+
remainingTargets);

vartargetContainer=<targets/>;
currentTargetSet=newXML(targetContainer);
currentTargetSet.targets=remainingTargets;

if(remainingTargets.length()==1)...{
//Makeaguess
}else...{


varremainingAnswers=currentTargetSet..answer.(@questionid>currentQuestion);

mostPopularQuestionCount=0;
mostPopularQuestionId=0;

get_most_popular_question(remainingAnswers);
currentQuestion=mostPopularQuestionId;
ask_question();
}
}

varmostPopularQuestionId=0;
varmostPopularQuestionCount=0;

functionget_most_popular_question(answersToCheck)...{

varanswersToCheckElement=<answersToCheckRoot/>;
varcheckElement=newXML(answersToCheckElement);
checkElement.appendChild(answersToCheck);
varfirstId=checkElement..answer[0].@questionid;

varthisQuestionCount=checkElement.answer.(@questionid==firstId).length();
if(thisQuestionCount>mostPopularQuestionCount)...{
mostPopularQuestionCount=thisQuestionCount;
mostPopularQuestionId=firstId;
}
answersToCheck=checkElement..answer.(@questionid!=firstId);

if(answersToCheck.length()>0)...{
get_most_popular_question(answersToCheck);
}else...{
//alert("Mostpopularquestionis"+mostPopularQuestionId+",
with"+mostPopularQuestionCount+"answers.")
}
}
...

如果排除了所有与用户的答案不相符的目标，只剩下一个东西，那么就该显示猜测的结果了，稍后讨论这个步骤。

另一方面，如果还剩下多个东西，那么首先需要重新构造 currentTargetSet；请记住，remainingTargets 仅仅是 target 元素的列表，所以第一步是创建一个新的文档，这个文档中有一个根元素，并把这些 target 元素添加到根元素中。

完成这个步骤之后，可以获得一个 XMLList，其中包含 questionid 大于当前问题的所有答案。需要从这些答案中选出最相关的问题。

为此，创建一个递归函数 get_most_popular_question()。每次运行时，它选择找到的第一个 questionid 值，然后检查当前集合中有多少个答案与这个问题相关。它检查这个问题计数值是否是目前最大的。如果当前集合中还有其他问题，就再次递归运行这个例程。

最后，把 currentQuestion 设置为最相关的问题，返回并提出这个问题。

在这个示例中，如果首先选择 Animal，那么会剩下两个目标，“a house cat” 和 “a dog”。排除问题 1 之后，最相关的问题是问题 2，“Does it bark?”。

做出猜测

用户回答了问题 “Does it bark” 之后，就只剩下一个目标了。无论答案是什么，现在都该做出猜测了，见清单 10。

清单 10. 做出猜测

...
vartargetContainer=<targets/>;
currentTargetSet=newXML(targetContainer);
currentTargetSet.targets=remainingTargets;

if(remainingTargets.length()==1)...{
currentGuessText=currentTargetSet.target.display;
currentGuessId=currentTargetSet.target.@id;
guess();
}else...{
varremainingAnswers=
currentTargetSet..answer.(@questionid>currentQuestion);
get_most_popular_question(remainingAnswers);
currentQuestion=mostPopularQuestionId;
ask_question();
}
}

varcurrentGuessText="";
varcurrentGuessId="";

functionguess()...{
document.getElementById("guessSpan").innerHTML=currentGuessText;
show_form("guessDiv");
}
...

如果已经可以做出猜测，那么 currentTargetSet 包含的内容就是猜测的结果，所以可以创建全局变量 currentGuessText 和 currentGuessId 并显示 guess div，见清单 11。

清单 11. 猜测表单

<divid="guessDiv"style="position:absolute;top:50px;visibility:hidden;
width:100%;">

It's<spanid="guessSpan"></span>,right?<br/>
<ahref="#"onclick="start_over()">YES!You'reright!
Letmetryagain.</a><br/>
<ahref="#"onclick="get_new_target()">No,sorry!</a><br/>

</div>

</body>
</html>

所以，如果选择 Animal，然后选择 Yes，应用程序应该会猜出 “a dog”，见图 6。

图 6. 第一个猜测

在第 2 部分中，我们将处理猜测错误的情况，现在看看在应用程序猜测正确的情况下应该怎么做。

猜测正确

start_over() 函数非常简单，见清单 12。

清单 12. 重新开始

                
function start_over(){
    hide_form("guessDiv"); 
    currentQuestion = 1;
    currentTargetSet = knowledgeBase.targets;
    ask_question();
}

为了重新开始游戏，需要隐藏 guess div，然后把 currentQuestion 和 currentTargetSet 复位，并返回到 ask_question()，再次显示第一个问题。

但是，如果猜测错误，应该怎么办？如果猜测错误，需要让系统学习正确的东西，在第 2 部分中将讨论具体实现方法。

后续改进

在本文中，您学习了如何使用 E4X 以 Twenty Questions 游戏的形式实现冒泡排序例程。学习了如何创建和操作 E4X XML() 对象和 XMLList() 对象，以及如何使用对象语法访问其中的数据。还学习了如何用过滤器限制给定集合中的节点。

但是，这个应用程序仍然非常简单。在真实的应用程序中，可能希望扩大有效答案的范围，包含 "sometimes" 或 "I don't know"，但是为了接受多个有效答案，不得不增加算法的复杂性。在本系列中，不做这一改进；如果您确实需要这么做，可以购买 20Q.net 算法的许可证（参见 参考资料）。在第 2 部分中，将把系统与一个后端数据库集成起来，让系统能够在用户玩游戏时学习新知识。

下载

描述 名字 大小 下载方法 第 1 部分源代码

x-e4xpart1code.zip	3KB	HTTP