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:
- typedef map<string,string> StringMap;
- string ConcurrentReplace(const string& text, const StringMap& phrases)
- {
- if (text.empty() || phrases.empty()) return text;
- stringstream ss;
- for (size_t i = 0; i < text.length(); )
- {
- StringMap::const_iterator phraseIt = phrases.end();
- size_t minPhrasePos = 0;
- for (StringMap::const_iterator it = phrases.begin();
- it != phrases.end(); ++it)
- {
- size_t phrasePos = text.find(it->first, i);
- if (phrasePos == string::npos) continue;
- if (phraseIt == phrases.end() || phrasePos < minPhrasePos)
- { phraseIt = it; minPhrasePos = phrasePos; }
- }
- if (phraseIt == phrases.end()) { ss << text.substr(i); break; }
- ss << text.substr(i, minPhrasePos - i);
- ss << phraseIt->second;
- i = minPhrasePos + phraseIt->first.length();
- }
- return ss.str();
- }
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).
-
Piotr Wach:
June 13th, 2010 o 9:25Ciekawy 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!:)
-
cp:
June 13th, 2010 o 18:57Z 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?
-
Xion:
June 13th, 2010 o 20:42Sł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.
-
Java:
June 16th, 2010 o 10:39A Boost.String_algo nie ma czegoś takiego?
Recent posts
