Posts tagged ‘find & replace’

Równoczesne zastępowanie kilku fraz w tekście

2010-06-12 23:22

Łańcuchy znaków w językach programowania udostępniają zwykle operację zamiany wszystkich wystąpień jednego podciągu na inny. Nawet jeśli tak nie jest (co dotyczy chociażby C++, jak zwykle), możliwe jest jej łatwe zaimplementowanie przy pomocy prostszych funkcji (jak choćby std::string::find).
Gorzej jest z nieco bardziej skomplikowaną procedurą zastępowania kilku fraz naraz. Zaznaczam od razu, że nie jest to wcale równoważne wywołaniu funkcji typu Replace parę razy dla różnych argumentów. Jeśli bowiem zastąpimy w tekście X1 przez Y1, a w wyniku X2 przez Y2, to możemy otrzymać inny rezultat niż przy dokonywaniu obu zamian równocześnie – wystarczy, że Y1 będzie w sobie zawierał ciąg X2. W celu uzyskania poprawnego wyniku należy wszystkie zamiany przeprowadzać jednocześnie.

Prosta implementacja takiej operacji może się sprowadzać do przeglądania tekstu w poszukiwaniu któregoś z podciągów do zastąpienia, a następnie dokonania faktycznej zamiany dla tego z nich, który został wykryty najwcześniej w stosunku do aktualnej pozycji w tekście. Należy następnie przesunąć się tuż za znalezioną frazę i działanie powtórzyć – i tak aż do końca tekstu. W C++ wygląda to wszystko mniej więcej tak:

  1. typedef map<string,string> StringMap;
  2. string ConcurrentReplace(const string& text, const StringMap& phrases)
  3. {
  4.     if (text.empty() || phrases.empty()) return text;
  5.  
  6.     stringstream ss;
  7.     for (size_t i = 0; i < text.length(); )
  8.     {
  9.         StringMap::const_iterator phraseIt = phrases.end();
  10.         size_t minPhrasePos = 0;
  11.         for (StringMap::const_iterator it = phrases.begin();
  12.             it != phrases.end(); ++it)
  13.         {
  14.             size_t phrasePos = text.find(it->first, i);
  15.             if (phrasePos == string::npos) continue;
  16.             if (phraseIt == phrases.end() || phrasePos < minPhrasePos)
  17.                 { phraseIt = it; minPhrasePos = phrasePos; }
  18.         }
  19.         if (phraseIt == phrases.end())   { ss << text.substr(i); break; }
  20.  
  21.         ss << text.substr(i, minPhrasePos - i);
  22.         ss << phraseIt->second;
  23.         i = minPhrasePos + phraseIt->first.length();
  24.     }
  25.     return ss.str();
  26. }

Jeśli tekst, na którym operujemy, ma długość n, a fraz do wyszukania i zastąpienia jest k, to w najgorszym przypadku całość może zabrać czas O(kn). Wymagałoby to jednak dość specyficznych danych, więc w praktyce nie musi być aż tak źle :) Dla lepszych rezultatów – zwłaszcza przy “obrabianiu” większej liczby tekstów tym samym słownikiem fraz – należałoby pewnie użyć specjalistycznych struktur danych, np. drzew prefiksowych (trie).

Tags: ,
Author: Xion, posted under Programming » 4 comments
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.