Поиск с помощью BFS - PullRequest
Новая
       18

Поиск с помощью BFS

1 голос
/ 14 августа 2011

Я получаю наборы из Wordnet и возвращаю его в виде массива. Это часть моего кода 

<pre>
RiWordnet wordnet = new RiWordnet();
String word = lineTF.getText();
// Get synsets
String[] synsets = wordnet.getAllSynsets(word, "n");
String outputSynset = "Word: " + word;

    GUIsynonymTA.append("\n");
    GUIsynonymTA.append(outputSynset);
    GUIsynonymTA.append("\n");

    if (synsets != null) 
    {

    for (int i = 0; i < synsets.length; i++) 
    {
    GUIsynonymTA.append("\n");
    GUIsynonymTA.append("Synsets " + i + ": " + (synsets[i]));                        
    GUIsynonymTA.append("\n");

    //implement BFS here
<code>

до этой строки я успешно извлек синтаксис. То, что я собираюсь сделать, это реализовать поиск в ширину в поиске синтаксиса WordNet. Я вызываю метод getAllSynsets из библиотеки RiWordnet, который хранит все синонимы в wordnet. Я пытаюсь использовать циклы (если ... еще), но я не уверен, где остановить поиск. Ожидается, что при использовании BFS будет определена область поиска, где синоним поиска будет помечен как посещенные узлы. Вот концепция, которую я хотел бы реализовать, используя BFS при поиске синонимов.

Например: 

student = {pupil, educatee, scholar, bookman} 

pupil = {student, educatee, schoolchild}

educatee = {student, pupil} --> has been search, so go to the next synonym.

schoolchild = {pupil} --> has been search, so go to the next synonym.

scholar = {bookman, student, learner, assimilator}

bookman = {scholar, student} --> has been search, so go to the next synonym.

learner = {scholar, assimilator, apprentice, prentice}

assimilator = {learner, scholar} --> has been search, so go to the next synonym.

apprentice = {learner} --> has been search, so go to the next synonym.

prentice = {apprentice, learner} --> has been search, so go to the next synonym.

ALL SYNONYM HAS BEEN SEARCH, SO STOP.

Некоторые люди также предложили мне использовать HashSet вместо BFS. Может кто-нибудь мне помочь? Заранее спасибо ..

1 Ответ

0 голосов
/ 04 сентября 2011

Звучит так, будто вы хотите что-то вроде этого: 

Queue<String> pending = ...
HashSet<String> processed = ...

pending.add("startWord"); 
processed.add("startWord");

while (!pending.isEmpty()) {
   String word = pending.remove();

   String[] possibilities = wordnet.getAllSynsets(word, "n");
   for (String p : possibilities) {
     // Make sure we haven't already processed the new word 
     if (!processed.contains(p)) {
        pending.add(p);
        processed.contains(p);
      }
   }
}

//  At this point, processed contains all synonyms found

Это более или менее рекурсивное расширение синонимов (что в сущности и есть BFS).

...