结构化设计：模块化编程与KWIC索引实现

### 结构化设计：模块化编程与KWIC索引实现 #### 1. 模块化编程基础 在编程领域，模块化设计是一种重要的编程思想。1972年，David Parnas提出了模块化编程的概念，他的论文不仅介绍了模块化设计，还引入了信息隐藏这一面向对象编程的关键技术。他强调了基于控制流的自上而下分解问题和利用封装与信息隐藏来隔离数据定义及其操作的分解方式之间的差异，这为后来的面向对象分析与设计（OOA&D）奠定了基础。 Parnas实际上讨论的是“关注点分离”的概念。在计算机科学中，关注点分离是将计算机程序分解为功能尽可能少重叠的不同特性的过程。传统上，关注点分离主要是分离程序的功能，而Parnas进一步提出分离数据，使得每个模块能够控制数据以及对数据的操作，并且数据只能通过明确定义的接口可见。 模块化编程有三个关键特性： - **封装**：将一组由数据和行为定义的服务捆绑在一起作为一个模块，并保持它们的整体性。模块应该具有高内聚性，即只做一件事，并且模块内的所有功能都朝着实现这一件事的目标工作。模块向用户提供一个接口，理想情况下，这是访问模块内服务和数据的唯一途径。 - **松耦合**：描述两个模块之间的关联强度。我们希望尽量减少一个模块对另一个模块的依赖，通过模块接口进行所有模块间的交互。松耦合可分为以下四类，从好到差依次为： - **简单数据耦合**：通过参数列表传递非结构化数据。这是最好的耦合方式，因为接收模块可以根据自身需求对数据进行结构化处理，并决定如何使用数据。 - **结构化数据耦合**：通过参数列表传递结构化数据。这也是一种较好的耦合方式，发送模块控制数据格式，接收模块可以自由处理数据。 - **控制耦合**：模块A的数据传递给模块B，数据内容告知模块B要做什么。这种耦合方式不好，因为模块A控制了模块B中函数的执行方式，两个模块过于紧密。 - **全局数据耦合**：两个模块使用相同的全局数据。这是最差的耦合方式，违反了封装的基本原则，会导致不必要的副作用，并且在程序执行的任何时刻，模块A和模块B都无法确切知道全局共享数据的状态。 - **信息隐藏**：常与封装混淆，但二者不同。封装是将数据和行为包装成一个实体（如模块），模块内的数据可以公开可见；而信息隐藏要求模块内的数据和行为仅对操作这些数据的内部操作可见，对外部模块不可见。这一特性保护了数据免受其他模块的干扰，确保数据由最了解如何操作它的模块控制。 Parnas的信息隐藏定义更关注在模块定义中隐藏设计决策。通过这种方式隐藏信息，模块的客户端可以成功使用模块，而无需了解模块构建过程中的设计决策，同时开发人员可以更改模块的实现而不影响客户端的使用。 #### 2. 上下文关键词（KWIC）索引问题 在早期的Unix系统中，文档分为八个不同的部分，整个手册以置换索引开头。由于Unix命令行工具的名称非常简洁，查找命令变得困难。例如，“cat”命令用于连接和打印文件，但如果只知道功能而不知道命令名称，就很难找到相应的命令。置换索引通过将命令描述中的大部分单词（忽略冠词）作为索引的一部分，解决了这个问题，这就是上下文关键词（KWIC）索引。 我们的问题是输入两个文件，一个包含要忽略的单词，另一个包含要索引的文本行，然后为它们创建KWIC索引。例如，忽略“for”、“the”、“and”等冠词，输入文件内容如下： ``` The Sun also Rises For Whom the Bell Tolls The Old Man and the Sea ``` 生成的KWIC索引如下： ``` The Sun ALSO Rises For Whom the BELL Tolls The Old MAN and the Sea The OLD Man and the Sea The Sun also RISES The Old Man and the SEA The SUN also Rises For Whom the Bell TOLLS For WHOM the Bell Tolls ``` 每个关键词都大写，输入行中的每个索引词都会使该行出现一次，并且关键词按字母顺序排序。通过循环移位使关键词可见，当索引词相同时，输入行按其在输入文件中的顺序排列。 #### 3. 自上而下的分解方法 我们可以使用自上而下的分解方法来设计解决方案。这种方法关注控制流，逐步解决问题。具体步骤如下： 1. **输入要忽略的单词和文本**：读取两个文件，一个包含要忽略的单词，另一个包含要索引的文本行。 2. **创建包含循环移位文本行的数据结构**：记录每行中哪个单词是索引词。 3. **按索引词对循环移位的文本行进行排序**：使用稳定的排序算法，确保相同索引词的行按输入文件中的顺序排列。 4. **格式化输出行**：根据选择的数据结构，对输出行进行格式化。 5. **输出文本**：将格式化后的文本输出。 这些步骤可以很容易地转换为从主程序顺序调用的五个子程序。输入文本的数据结构可以是每行的字符数组、每行的字符串或整个输入文件的字符串数组，也可以使用映射数据结构，其中每个索引词作为键，包含输入文本行的字符串作为值。排序算法的选择取决于所选的数据结构和输入文本的预期大小。 #### 4. KWIC问题的模块化分解 KWIC问题的模块化分解基于信息隐藏，隐藏数据结构和设计决策。以下是一组用于KWIC问题的模块： - **Line模块**：处理输入文本行的数据存储，包括当前行、关键词和关键词在该行中的索引。 - **Keyword - Line对模块**：辅助Line模块创建数据结构。 - **KWICIndex模块**：创建索引列表，处理循环移位和排序。 - **Circular Shift模块**：执行循环移位操作。 - **格式化和打印输出模块**：对关键词行进行格式化，使关键词大写并居中。 - **主控制模块（主程序）**：读取输入，创建KWICIndex对象，并调用打印方法。 这些模块之间可以相互协作，并且可以在不了解每个模块具体实现和数据存储方式的情况下描述它们的交互。 #### 5. Java实现KWIC索引程序 以下是一个用Java实现的KWIC索引程序： ```java /** * CLASS Line * Handle the storage of 3 key pieces of information. * the current line, the keyword, and the index of the * keyword in the line. * * Basically just like a struct in C. * */ public class Line implements Comparable<Line> { public String line; public String keyword; public int indexOf; public Line(String line, String keyword, int indexOf) { this.keyword = keyword; this.indexOf = indexOf; // capitalize the keyword in the line // grab the first part of the line String first = line.substring(0, indexOf); // capitalize the entire keyword String middle = keyword.toUpperCase(); // grab the rest of the line after the keyword String last = line.substring(indexOf + keyword.length()); // put it all back together this.line = first + middle + last; } /** * We want to sort lines based on keyword alone. * This will do a lexicographical comparison of the keywords * Remember that keyword is a String */ @Override public int compareTo(Line other) { return this.keyword.compareToIgnoreCase(other.keyword); } } import java.util.Scanner; import java.util.*; /** * CLASS KwicIndex * A KwicIndex object contains a collection of Lines * and the words we are ignoring as keywords. * * We use a HashSet for the words to ignore because * we only ever want one of each of these words. * * We use a Pr ```