문자열 선형 검색 C#

Question

저는 현재 텍스트 파일에서 관련 용어/단어를 검색하는 작은 C# 연습을하고 있으며 프로그램은 검색된 단어가 포함 된 텍스트 파일의 모든 문장을 작성합니다. 예를 들어, "example"이라는 단어를 입력하면 프로그램에서 텍스트 파일의 모든 문장을 살펴보고 "example"이라는 단어가있는 문장을 꺼냅니다. 내가 할 수 있도록하고 싶습니다 무엇

The text file is structured as so: <sentenceDesignator> <text> 
sentence 1: bla bla bla bla example of a sentence //each line contains a sentence 
sentence 2: this is not a good example of grammar 
sentence 3: bla is not a real word, use better terms 

텍스트 파일의 모든 라인을 통해 이동하고 검색 문자열의 용어를 포함하는 모든 문장을 작성하는 선형 검색을 사용합니다. 지금까지

내 코드 : 파일의 인덱스를 구축 한 다음 색인을 가진 반면, 모든 검색 작업이 O(n)하는 선형 검색과 마찬가지로 인덱스를 검색 할 경우가 훨씬 더 빨리 될 것

 String filename = @"sentences.txt"; 

     if (!File.Exists(filename)) 
     { 
      // Since we just created the file, this shouldn't happen. 
      Console.WriteLine("{0} not found", filename); 
      return; 
     } 
     else 
     { 
      Console.WriteLine("Successfully found {0}.", filename); 
     } 
     //making a listof type "Sentence" to hold all the sentences 
     List<Sentence> sentences = new List<Sentence>(); 

     //the next lines of code... 
     StreamReader reader = File.OpenText(filename); 

     //first, write out all of the sentences in the text file 

     //read a line(sentence) from a line in the text file 
     string line = reader.ReadLine(); 

     while (line != null) 
     { 
      Sentence s = new Sentence(); 

      //we need something to split data... 
      string[] lineArray = line.Split(':'); 

      s.sentenceDesignator = lineArray[0]; 
      s.Text = lineArray[1]; 

      Console.Write("\n{0}", line); 

      line = reader.ReadLine(); 
     } 

     //so far, we can write out all of the sentences in the text file. 
     Console.Write("\n\nOK!, search a term to diplay all their occurences: "); 
     string searchTerm = Console.ReadLine(); 

     if(!line.Contains(searchterm)) 
     { 
      Console.Write("\nThat term does not exist in any sentence."); 
     } 
     else 
     { 
      foreach (Sentence ss in sentences) 
      { 
       if (ss.sentenceDesignator.Contains(queryName)) 
       { 
        //I need help here 
       } 
      } 
     } 

Answer 1

인덱스 구성을 위해 O(n)을 검색하십시오.하지만 인덱스를 작성하는 방법에 따라 검색을 위해 O(log n) 또는 near-O(1)을 조회하십시오. 비용은 인덱스 메모리 소비를 증가,하지만 난 이런 식으로 할 거라고 :

private Dictionary<String,List<Int32>> _index = new Dictionary<String,List<Int32>>(); 

/// <summary>Populates an index of words in a text file. Takes O(n) where n is the size of the input text file.</summary> 
public void BuildIndex(String fileName) { 

    using(Stream inputTextFile = OpenFile(...)) { 

     int currentPosition = 0; 
     foreach(String word in GetWords(inputTextFile)) { 

      word = word.ToUpperInvariant(); 
      if(!_index.ContainsKey(word)) _index.Add(word, new List<Int32>()); 
      _index[word].Add(currentPosition); 

      currentPosition = inputTextFile.Position; 
     } 
    } 
} 

/// <summary>Searches the text file (via its index) if the specified string (in its entirety) exists in the document. If so, it returns the position in the document where the string starts. Otherwise it returns -1. Lookup time is O(1) on the size of the input text file, and O(n) for the length of the query string.</summary> 
public Int32 SearchIndex(String query) { 

    String[] terms = query.Split(' '); 

    Int32 startingPosition = -1; 
    Int32 currentPosition = -1; 
    Boolean first = true; 
    foreach(String term in terms) { 
     term = term.ToUpperInvariant(); 

     if(first) { 
      if(!_index.Contains(term)) return -1; 
      startingPosition = _index[term][0]; 
     } else { 

      if(!ContainsTerm(term, ++currentPosition)) return -1; 
     } 

     first = false; 
    } 

    return startingPosition; 
} 

/// <summary>Indicates if the specified term exists at the specified position.</summary> 
private Boolean ContainsTerm(String term, Int32 expectedPosition) { 

    if(!_index.ContainsKey(term)) return false; 
    List<Int32> positions = _index[term]; 
    foreach(Int32 pos in positions) { 

     if(pos == expectedPosition) return true; 
    } 
    return false; 
} 

OpenFile 및 GetWords의 구현은 사소한해야한다. GetWords은 yield return을 사용하여 파일에 공백으로 구분 된 단어의 IEnumerable<String>을 작성하고 사용자 지정 파일 형식을 처리합니다.

Answer 2

마지막 if/else에 대해 약간 혼란 스럽습니다. 파일의 마지막 줄만을 searchterm과 비교하는 것 같습니다. 또한 "queryName"은 어디에서 왔습니까? 그리고 당신은 전체 문장 ("bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla bla")이나 " 또한 sentenceDesignator에 queryName이 포함되어 있는지 확인합니다. 실제 텍스트에 searchterm이 있는지 확인하고 싶습니다.

어쩌면 이것은 당신을 도울 것입니다 :

var lines = File.ReadAllLines(fileName);  
var sentences = new List<Sentence>(lines.Count()); 

foreach (var line in lines) 
{ 
    var lineArray = line.Split(':'); 
    sentences.Add(new Sentence { sentenceDesignator = lineArray[0], Text = lineArray[1]}); 
} 

foreach (var sentence in sentences) 
{ 
    if (sentence.Text.Contains(searchTerm)) 
    { 
     Console.WriteLine(sentence.sentenceDesignator); 
     //Console.WriteLine(sentence.Text); 
    } 
}