级别： 中级 Nicholas Chase (ibmquestions@nicholaschase.com), 自由撰稿人, 自由职业
2008 年 2 月 25 日 XML 似乎是用来传递 Ajax 数据的自然格式。但是，在 JavaScript 中使用 Document Object Model（DOM）处理 XML 不一定是最好的方法。因此还出现了其他选择，比如 JSON，这种格式对于开发人员来说更有对象的感觉。现在，ECMAScript for XML（E4X）组合了许多最好的 DOM 特性和极其简单的数据绑定，为在浏览器中处理 XML 提供了一种更简便的方法。在这个分两部分的文章系列中，您将学习如何用 E4X 和 Prototype JavaScript 库创建一个简单的 Ajax 读心术应用程序，这个程序实现 Twenty Questions 游戏，并可以在游戏过程中学习新东西。第 1 部分将创建一个系统，它接受并分析一个现有的知识库，从而判断用户可能在想什么。
完成后的应用程序 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 个不同的 “是/否” 问题进行排除，最终就可以找到一个东西。
| |
请访问 Ajax 技术资源中心，这是有关 Ajax 编程模型信息的一站式中心，包括很多文档、教程、论坛、blog、wiki 和新闻。任何 Ajax 的新信息都能在这里找到。
|
|
在第 1 部分中，将构建一个自包含的系统，它从一个固定的知识库开始，然后向用户提问来判断用户心里想的东西。在第 2 部分中，将对系统进行培训，让它学习新东西。如果系统猜错了，系统会询问正确的东西以及如何从知识库中区分出它。然后，它把新知识添加到知识库中并重新开始。最后，将把这个功能与一个外部数据库集成起来，从而存储系统从所有用户那里学到的东西。
算法
说起来容易，但是究竟如何在浏览器中实现 Twenty Questions 呢？如果人与人之间玩这个游戏，提问人可以凭借经验决定下一个问题；计算机如何做出决定呢？
实际上很简单。二分查找算法 — 或更一般的分治算法 — 用每个问题排除大约一半儿的可能选择。例如，如果最初有 1024 个可能的选择，那么第一个问题把范围缩小到 512 个，第二个问题把范围缩小到 256 个，第三个问题把范围缩小到 128 个，以此类推。对于 1024 个可能的选择，只需要 10 个问题就可以找到目标。实际上，20 个问题可以区分 1,048,576 个不同的选择！
实际上，算法并不复杂。算法如下：
- 装载知识库中的所有东西。
- 询问用户他心里想的东西是 “动物、植物还是矿物？”
应用程序使用的其他问题都要求回答是或否，但是这个问题是传统的 “第一个问题”，它可以排除大约 2/3 的可能选择。
- 排除所有与这个问题的回答不相符的东西。
- 如果范围已经收窄到一个东西，就询问用户这个猜测是否正确。
如果正确，就重新装载知识库并重新开始游戏。如果不正确，就询问用户究竟是什么东西，并要求用户提供一个可以区分正确答案和错误答案的问题。将这些信息添加到知识库中。（将在第 2 部分中完成这一步骤。）
- 如果仍然有多个东西，就要决定一个问题，这个问题应该应用于当前范围中尽可能多的东西。（这是关键；这样可以排除尽可能多的可能选择。）
- 提出这个问题。
- 返回到第 3 步。
E4X 非常适合实现这种算法。
注意：糟糕的是，无法强制用户向知识库中添加正确的信息，而提供错误信息的用户实际上使他们的内容无从查找。
E4X 简介
在编程环境中考虑处理 XML 时，您首先会想到什么？DOM？XPath？您首先想到的也许是 “哎唷，这真让人头疼！” 是的，确实是这样；XML 是一种出色的数据存储格式，但是处理 XML 却让人很头疼。但是，如果能够创建 XML 对象，轻松地访问和过滤 XML 节点，轻松地把数据序列化成显示或存储所需的字符串，那么会怎么样呢？您就不那么头疼了吧？
这就是 E4X 的价值所在。
E4X 使用一种与数据绑定相似的结构，简化了对 XML 文档的访问方法。请考虑下面这个片段（见清单 1）。
清单 1. 使用 E4X
<script type="text/javascript;e4x=1">
myquestion = <question>
<display>Is it animal, vegetable, or mineral?</display>
<answerOption>Animal</answerOption>
<answerOption>Vegetable</answerOption>
<answerOption>Mineral</answerOption>
</question>;
alert("The question is '" + 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>
<question id="1">
<display>Is it animal, vegetable, or mineral?</display>
<answerOption>Animal</answerOption>
<answerOption>Vegetable</answerOption>
<answerOption>Mineral</answerOption>
</question>
<question id="2">
<display>Does it bark?</display>
<answerOption>Yes</answerOption>
<answerOption>No</answerOption>
</question>
</questions>
<targets>
<target id="1">
<display>a house cat</display>
<answer questionid="1"><answerValue1>Animal</
answerValue1></answer>
<answer questionid="2"><answerValue2>No</
answerValue2></answer>
</target>
<target id="4">
<display>a dog</display>
<answer questionid="1"><answerValue1>Animal</
answerValue1></answer>
<answer questionid="2"><answerValue2>Yes</
answerValue2></answer>
</target>
<target id="2">
<display>a carrot</display>
<answer questionid="1"><answerValue1>Vegetable</
answerValue1></answer>
</target>
<target id="3">
<display>a ruby</display>
<answer questionid="1"><answerValue1>Mineral</
answerValue1></answer>
</target>
</targets>
</knowledgebase>;
knowledgeBase = new XML(kdata);
|
在继续开发之前，先仔细看看这个结构，因为它包含算法的关键。首先，这个文档包含问题和目标。问题很简单；每个问题包含实际的问题和可能的答案。除了第一个问题之外，其他所有问题的答案只有 “yes” 和 “no”。这个结构允许以后添加可能的答案。
目标包含一个目标标识符（id）、目标的显示名以及系统知道的每个问题的答案。例如，它知道狗是一种动物而且狗会吠叫，而对于胡萝卜，它只知道胡萝卜是植物。当然，知道这么多就够了；因为植物是不会吠叫的！
在系统学习新的问题和答案时，会在现有的目标中添加它们。
提示：如果需要更智能化的知识库，可以从 http://backstop.nicholaschase.com/knowledgebase.php?getkb=YES 下载当前的知识库。
显示问题
下一步是提出第一个问题。为此，需要显示它。一种简便方法是创建一个可定制的 HTML，见清单 4。
清单 4. 问题表单
<html>
<head>
<title>E4X mindreader</title>
<script type="text/javascript; e4x=1" src="e4x.js"></script>
<style type="text/css">
.answerLink {color: blue; text-decoration: underline}
</style>
</head>
<body style="background-color:#abdfe7;" onload="ask_question()">
<div id="questionFormDiv"
style="position: absolute;top: 50px;visibility: hidden; width: 100%;">
<span id="displayQuestion"></span><br />
</div>
</body>
</html>
|
这里有一个可以打开和关闭的 div（最初是关闭 的），其中有一个用来插入文本的 span。为了插入文本，需要能够选择一个特定的 XML 元素。
过滤节点
通过 E4X，可以用过滤器选择一个或多个节点，见清单 5。
清单 5. 使用过滤器
...
knowledgeBase = new XML(kdata);
var currentQuestion = 1;
//******************************
// BEGIN FUNCTIONS HERE
//******************************
function ask_question(){
var questionElement = knowledgeBase.questions.question.(@id == currentQuestion)
var questionDisplay = questionElement.display;
document.getElementById("displayQuestion").innerHTML = questionDisplay ;
show_form("questionFormDiv");
}
function hide_form(divName){
document.getElementById(divName).style.visibility = "hidden" ;
}
function show_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. 答案
<span id="displayQuestion"></span><br />
<span class="answerLink"
onclick="answer_question(this)" id="answer1Text"></span>
<span class="answerLink"
onclick="answer_question(this)" id="answer2Text"></span>
<span class="answerLink"
onclick="answer_question(this)" id="answer3Text"></span>
|
这些链接引用 answer_question() 函数（稍后编写这个函数）。但是，首先需要填充答案，见清单 7。
清单 7. 填充答案
...
document.getElementById("displayQuestion").innerHTML = questionDisplay ;
var answerOptions = new XMLList();
answerOptions = questionElement.answerOption;
var answerCounter = 0;
document.getElementById("answer3Text").innerHTML = "";
for each( var answerText in answerOptions) {
answerCounter++;
document.getElementById("answer"+answerCounter+"Text").innerHTML =
answerText;
}
}
...
|
answerOptions 变量包含一个 XMLList，它与 DOM Nodelist 相似。在这个示例中，它包含当前 questionElement 中的所有 answerOption 元素。然后，可以在一个 for each 循环中使用这个列表，引用每个元素并把它添加到适当的 span 中。（首先清除第三个 span，因为在显示第一个问题之后，就不再使用它了。）
在完成的页面上，对于每个 answerOption 元素有一个链接，见图 4。
图 4. 第一个问题
那么，当用户回答这个问题时，会发生什么？
回答问题
当用户回答问题时，需要过滤掉与问题的答案不相符的所有东西。首先，需要获得当前要考虑的一组目标，见清单 8。
清单 8. 获得当前目标
...
var currentQuestion = 1;
var currentTargetSet = knowledgeBase.targets;
//******************************
// BEGIN FUNCTIONS HERE
//******************************
function ask_question(){
...
}
function answer_question(answerSpan){
hide_form("questionFormDiv");
var theAnswer = answerSpan.innerHTML;
var remainingTargets =
currentTargetSet..target.(answer["answerValue"+currentQuestion]==theAnswer);
alert("There are "+remainingTargets.length()+" targets remaining: \n" +
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. 排除已经问过的问题
...
var remainingTargets =
currentTargetSet..target.(answer["answerValue"+currentQuestion] == theAnswer);
alert("There are "+remainingTargets.length()+" targets remaining: \n" +
remainingTargets);
var targetContainer = <targets/>;
currentTargetSet = new XML(targetContainer);
currentTargetSet.targets = remainingTargets;
if (remainingTargets.length() == 1){
// Make a guess
} else {
var remainingAnswers = currentTargetSet..answer.(@questionid > currentQuestion);
mostPopularQuestionCount = 0;
mostPopularQuestionId = 0;
get_most_popular_question(remainingAnswers);
currentQuestion = mostPopularQuestionId;
ask_question();
}
}
var mostPopularQuestionId = 0;
var mostPopularQuestionCount = 0;
function get_most_popular_question(answersToCheck){
var answersToCheckElement = <answersToCheckRoot/>;
var checkElement = new XML(answersToCheckElement);
checkElement.appendChild(answersToCheck);
var firstId = checkElement..answer[0].@questionid;
var thisQuestionCount = 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("Most popular question is "+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. 做出猜测
...
var targetContainer = <targets/>;
currentTargetSet = new XML(targetContainer);
currentTargetSet.targets = remainingTargets;
if (remainingTargets.length() == 1){
currentGuessText = currentTargetSet.target.display;
currentGuessId = currentTargetSet.target.@id;
guess();
} else {
var remainingAnswers =
currentTargetSet..answer.(@questionid > currentQuestion);
get_most_popular_question(remainingAnswers);
currentQuestion = mostPopularQuestionId;
ask_question();
}
}
var currentGuessText = "";
var currentGuessId = "";
function guess(){
document.getElementById("guessSpan").innerHTML = currentGuessText;
show_form("guessDiv");
}
...
|
如果已经可以做出猜测，那么 currentTargetSet 包含的内容就是猜测的结果，所以可以创建全局变量 currentGuessText 和 currentGuessId 并显示 guess div，见清单 11。
清单 11. 猜测表单
<div id="guessDiv" style="position: absolute; top: 50px;visibility: hidden;
width: 100%;">
It's <span id="guessSpan"></span>, right?<br />
<a href="#" onclick="start_over()">YES! You're right!
Let me try again.</a><br />
<a href="#" 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 |
|---|
参考资料 学习
获得产品和技术
-
IBM 试用版软件：使用这些可以从 developerWorks 直接下载的试用版软件构建您的下一个开发项目。
讨论
关于作者 | | | Nicholas Chase 曾经参与多家公司的网站开发，包括 Lucent Technologies、Sun Microsystems、Oracle 和 Tampa Bay Buccaneers。Nick 曾经做过高中物理教师、低放射性废弃设备管理员、在线科幻杂志的编辑、多媒体工程师、Oracle 教员以及一家交互通信公司的首席技术官。他出版了多部著作，包括 XML Primer Plus（Sams）。他还是 InterSection Unlimited 的合伙人，这家公司从事 Second Life 内容和应用程序的创建。在 Second Life 中，他的名字是 Chase Marellan。 |
对本文的评价
| 
