C# büyük metin dosyasını arıyor

Question

Büyük bir metin dosyasında (300-600mb) bir dizgiyi aramaya çalışıyorum. Benim mevcut yöntemimi kullanarak, çok uzun sürüyor.

Şu anda dize aramak için IndexOf kullanıyordum, ancak bu süre, dizeyle her satır için bir dizin oluşturmak için çok uzun (20s) yoldur.

Arama hızını nasıl en iyi duruma getirebilirim? Ben Contains() denedim ama bu da yavaş. Baska öneri? Regex maçı düşünüyordum ama önemli bir hız artışı olduğunu görmüyorum. Belki benim arama mantık örneği

while ((line = myStream.ReadLine()) != null) 
{ 
    if (line.IndexOf(CompareString, StringComparison.OrdinalIgnoreCase) >= 0) 
    { 
     LineIndex.Add(CurrentPosition); 
     LinesCounted += 1; 
    } 
} 

Answer 1

size gerçekleştirdiğini kullandığınız kaba kuvvet algoritması n dize uzunluğudur (nm) kez arandığını Ç ve Bulmaya çalıştığınız alt dizenin/desenin uzunluğu m. Bir dize arama algoritması kullanmak gerekir:

• Boyer-Moore "standart" Bence: http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

• Ama çok daha fazla orada vardır: http://www-igm.univ-mlv.fr/~lecroq/string/

Dahil olmak üzere

• Morris-Pratt dahil: http://www.stoimen.com/blog/2012/04/09/computer-algorithms-morris-pratt-string-searching/

• ve Knuth-Morris-Pratt: http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

Ancak dikkatli ile hazırlanmış normal bir ifade kullanarak bulmaya çalıştığınız ne bağlı yeterli olabilir. Verimli etkili ifadeler oluşturma konusunda yardım için Jeffrey's Friedl ürününün Mastering Regular Expressions numaralı telefonuna bakın (örn. Geri izleme yok).

Ayrıca iyi bir algoritma metnine başvurmak isteyebilirsiniz. I ([| C++ | C, Java] içinde Algoritmalar) Robert Sedgewick en Algorithms onun various incarnations yılında kısmi değilim

Answer 2

Bu soruları (ve cevaplar) gördünüz mü

kusurludur? Eğer şimdi olduğu gibi yapmak Is there a way to read large text file in parts?

Matching a string in a Large text file?

Processing large text file in C#

• yapmak istediğiniz tüm metin dosyasını okumak ise gitmek için bir yol olarak görünmektedir. Diğer fikirler:

  • böyle o metin dosyasına eklenen aldığında olarak önceden sıralamak veri, mümkün olursa, o yardımcı olabilir. Verileri bir veritabanına ekleyebilir ve gerektiği şekilde sorgulayabilirsiniz.

  • Bir karma tablosunu kullanabilirsiniz

Answer 3

yapabilirsiniz kullanıcı regexp.Match (String). RegExp Match daha hızlıdır.

static void Main()

{

string text = "One car red car blue car"; 
    string pat = @"(\w+)\s+(car)"; 

    // Instantiate the regular expression object. 
    Regex r = new Regex(pat, RegexOptions.IgnoreCase); 

    // Match the regular expression pattern against a text string. 
    Match m = r.Match(text); 
    int matchCount = 0; 
    while (m.Success) 
    { 
    Console.WriteLine("Match"+ (++matchCount)); 
    for (int i = 1; i <= 2; i++) 
    { 
     Group g = m.Groups[i]; 
     Console.WriteLine("Group"+i+"='" + g + "'"); 
     CaptureCollection cc = g.Captures; 
     for (int j = 0; j < cc.Count; j++) 
     { 
      Capture c = cc[j]; 
      System.Console.WriteLine("Capture"+j+"='" + c + "', Position="+c.Index); 
     } 
    } 
    m = m.NextMatch(); 
    } 

}

Answer 4

Maalesef, düz yolda C# yapabileceğiniz bir sürü var sanmıyorum.

Bu görev için son derece hızlı olması için Boyer-Moore algoritmasını buldum. Ama ben IndexOf kadar hızlı bile yapmanın bir yolu olmadığını buldum. Benim varsayımım, kodum C# ile çalıştırılırken, bunun IndexOf el ile optimize edilmiş assembler'da uygulanmasından kaynaklanmasıdır.

Kodumu ve performans sınama sonuçlarını Fast Text Search with Boyer-Moore numaralı makalede görebilirsiniz.