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 for post “Równoczesne zastępowanie kilku fraz w tekście”.
  1. Piotr Wach:
    June 13th, 2010 o 9:25

    Ciekawy algorytm, może się przydać :)

    Zaglądałem do strony linki i zauważyłem, że 50% jest już nie aktualnych. Oczywiście najbardziej zależ mi na aktualnym odnośniku do mojego bloga, więc jeślibyś mógł podlinkować mój aktualny adres http://mobiledev.pl byłoby super :) Dzięki!:)

  2. cp:
    June 13th, 2010 o 18:57

    Z innej beczki: widze Xion, ze wlaczyles skrotowe wyswietlanie tresci w RSSach. Jest to o niebo mniej wygodne od calych notek, jak to bylo do tej pory i zapewne nie tylko ja tak uwazam. Moglbys przywrocic stare rozwiazanie badz ewentualnie udostepnic chociaz dwa kanaly?

  3. Xion:
    June 13th, 2010 o 20:42

    Słyszałem po prostu, że RSS z całymi notkami się dość długo wczytuje, więc wypróbowałem takie rozwiązanie. Ale widzę, że z dwojga złego już lepiej dawać całość (zwłaszcza że niestety ale WordPress nie daje opcji określenia, ile znaków posta ma być udostępniane w RSSie).

    A co do strony z linkami: przyznaję, że ostatnio jej nie sprawdzałem :) Muszę nadrobić zaległości.

  4. Java:
    June 16th, 2010 o 10:39

    A Boost.String_algo nie ma czegoś takiego?

Comments are disabled.
 


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