Section 7.4. Example: Keyword Search


[Page 315 (continued)]

7.4. Example: Keyword Search

One of the most widely used Web browser functions is the search utility. You probably know how it works. You type in a keyword and click on a button, and it returns with a list of Web pages that contain the keyword.

Suppose you were writing a browser in Java. How would you implement this function? Of course, we don't know yet how to read files or Web pages, and we won't cover that until Chapter 11. But for now, we can write a method that will search a string for all occurrences of a given keyword. That's at least part of the task that the browser's search engine would have to do.

So we want a method, keywordSearch(), that takes two String parameters, one for the string that's being searched, and the other representing the keyword. Let's have the method return a String that lists the number of keyword occurrences, followed by the index of each occurrence. For example, if we asked this method to find all occurrences of is in "This is a test", it should return the string "2: 2 5" because there are two occurrences of is in the string, one starting at index 2 and the other at index 5.

Method design


Algorithm design


The algorithm for this method will require a loop, because we want to know the location of every occurrence of the keyword in the string. One way to do this would be to use the indexOf() method to search for the location of substrings in the string. If it finds the keyword at index N, it should record the location and then continue searching for more occurrences starting at index N + 1 in the string. It should continue in this way until there are no more occurrences.


[Page 316]

Suppose S is our string and K is the keyword. Initialize a counter variable and result string. Set Ptr to the indexOf() the first occurrence of K in S. While (Ptr != -1)     Increment the counter     Insert Ptr into the result string     Set Ptr to the next location of the keyword in S Insert the count into the result string Return the result string as a String 


As this pseudocode shows, the algorithm uses a while loop with a sentinel bound.The algorithm terminates when the indexOf() method returns a -1, indicating that there are no more occurrences of the keyword in the string.

Implementation


Translating the pseudocode into Java gives us the method shown in Figure 7.8. Note how string concatenation is used to build the resultStr. Each time an occurrence is found, its location (ptr) is concatenated to the right-hand side of the resultStr. When the loop terminates, the number of occurrences (count) is concatenated to the left-hand side of the resultStr.

Figure 7.8. The keywordSearch() method.

  /**   * Pre:  s and keyword are any Strings   * Post: keywordSearch() returns a String containing the   *  number of occurrences of keyword in s, followed   *  by the starting location of each occurrence   */ public String keywordSearch(String s, String keyword) {   String resultStr = "";   int count = 0;   int ptr = s.indexOf(keyword);   while (ptr != -1) {     ++count;     resultStr = resultStr + ptr + " ";     ptr = s.indexOf(keyword, ptr + 1);   // Next occurrence   }   resultStr = count + ": " + resultStr;  // Insert the count   return resultStr;                      // Return as a String } // keywordSearch() 

Testing and Debugging

What test data do we need?


What test data should we use for the keywordSearch() method? One important consideration in this case is to test whether the method works for all possible locations of the keyword within the string. Thus, the method should be tested on strings that contain keyword occurrences at the beginning, middle, and end of the string. We should also test the method with a string that doesn't contain the keyword. Such tests will help verify that the loop will terminate properly in all cases. Given these considerations, Table 7.1 shows the tests that were made. As you can see from these results, the method did produce the expected outcomes. While these tests do not guarantee its correctness, they provide considerable evidence that the algorithm works correctly.


[Page 317]

Table 7.1. Testing the keywordSearch() method

Test Performed

Expected Result

keywordSearch("this is a test","is")

2: 2 5

keywordSearch("able was i ere i saw elba","a")

4: 0 6 18 24

keywordSearch("this is a test","taste")

0:


Effective Design: Test Data

In designing test data to check the correctness of a string-searching algorithm, it's important to use data that test all possible outcomes.





Java, Java, Java(c) Object-Orienting Problem Solving
Java, Java, Java, Object-Oriented Problem Solving (3rd Edition)
ISBN: 0131474340
EAN: 2147483647
Year: 2005
Pages: 275

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net