Konserviertheit eines Strings ermitteln

Jay1980

Servus,

ich will ab einer Grenze von 90 % Konserviertheit den String entwerten. Der String AAAAAAAAABA, sollte also raus, weil A zu oft vorkommt.

Wie prüfe ich da ein Bündel von Strings möglichst geschickt durch?

Skym0sh0

zähl die buchstaben und rechne das vorkommen in przent aus
also bei diesem string hier:
aaab -> 3a von 4 buchstaben ==> 75% a's (formel: anzahl/länge *100)

Jay1980

Okay, also ich nehme das erste Symbol und zähle das Vorkommen von diesem. Dann vergleiche ich, ob das Auftreten die vorher berechnete Schwelle gesprengt hat. Hat es diese Schwelle gesprengt, nehme ich das nächste Symbol, bis keine unbekannten Symbole mehr da sind. Zeitgleich kann ich die bereits bekannten Symbole mitnotieren und wenn die 10 % überschritten sind ausbrechen und das Gezähle aufhören für diesen String ...

Hat da jemand noch ein geschickteres Vorgehen parat?

SeppJ

Jay1980 schrieb:

Hat da jemand noch ein geschickteres Vorgehen parat?

Du gehst den String 1x durch und zählst jede Symbolsorte mit (eine map bietet sich an). Wenn eine Symbolsorte die geforderte Höchsmenge überschreitet, brichst du ab.

Jay1980

Sehr gut mit dem 'einmal durchgehen' - hier ist mein Versuch:

void flagImportantColumnsRelatedToIdentity() // TODO umbenennen, dass es um Konsverviertheit geht
    {

        // Methode erkennt Spaltenstrings von mehr als 90 % Konserviertheit und kennzeichnet diese

        cout << "main - flagImportantColumnsRelatedToIdentity() ....\n";

        // Map-Verwendung, Spaltenstring-Bildung, siehe Single-Entropie-Berechnung
        typedef map< char, int > SoMapType;
        typedef SoMapType::value_type SoValuePair;
        SoMapType symbolOccuranceList; // eine Liste pro Spalte
        vector< SoMapType > listOfMaps;
        int msaColCounter = 0;
        int msaRowCounter = 0;
        int msaCols = seqan::length(this->getSequencesList()[ 0 ]);
        int msaRows = seqan::length(this->getSequencesList());
        seqan::CharString currentSequenceString;
        double schwelle = msaRows * 0.9;
        cout << "... Schwelle liegt bei " << schwelle << endl; // Schwelle ermitteln
        seqan::StringSet<seqan::CharString> colStringList; // TODO in der Methode geht es ohne, aber wenn ich diese Speicher dann hier denke ich.

        // Spalten-Strings bilden, TODO überdenken, ob ich die Spaltenstrings nicht irgendwo direkt ablegen sollte
        for ( msaRowCounter = 0; msaRowCounter < msaRows; msaRowCounter++)
        {
            if ( msaRowCounter == 0 )
            {
                // Anlegen einer Map pro Spalte
                int mapColCounter = 0; 
                for ( mapColCounter = 0; mapColCounter < msaCols; mapColCounter++ )
                {
                    SoMapType symbolOccuranceList;
                    listOfMaps.push_back( symbolOccuranceList );
                }
                cout << "... eine Map pro Spalte wurde angelegt, gesamt " << listOfMaps.size() << endl;
            }

            currentSequenceString = seqan::value( this->getSequencesList(), msaRowCounter );
            cout << "... picke currentSequenceString, hier " << currentSequenceString << endl;

            char currentChar; // das gepickte Zeichen des Sequenzstrings
            SoMapType currentMap;
            for ( msaColCounter = 0; msaColCounter < msaCols; msaColCounter++ )
            {
                currentMap = listOfMaps.at(msaColCounter);
                cout << "... aktuelle Map gewählt. \n";
                //cout << currentMap << endl;

                currentChar = currentSequenceString[ msaColCounter ];
                cout << "... ... currentChar: " << currentChar << "; Spalte " << msaColCounter << endl;

                // Mapping-Vorgang
                SoMapType::const_iterator soIter;
                soIter = currentMap.find( currentChar );
                if ( soIter != currentMap.end() )
                {
                    currentMap[ currentChar ] += 1;
                    cout << "... ... Map zu currentChar [key|value][" << currentChar << "|" << currentMap[ currentChar ] <<  "] existiert für currentSequenceString!\n";
                    // check fuer den aktuellen Key-Value, ob die Schwelle schon erreicht ist
                    if ( currentMap[ currentChar ] > schwelle )
                    {
                        importantColumns.at( msaColCounter ) = 1; // unwichtig
                        cout << "... ... ... Schwellwert für " << currentChar << " getoppt, setze Spalte " << msaColCounter << " auf 1 \n";
                    }
                }
                else // noch nicht drin
                {
                    currentMap.insert( SoValuePair( currentChar, 1 ) );
                    cout << "... ... Map zu currentChar [key|value][" << currentChar << "|" << currentMap[ currentChar ] <<  "] ist neu für currentSequenceString!\n";

                    // check fuer den aktuellen Key-Value, ob die Schwelle schon erreicht ist
                    if ( symbolOccuranceList[ currentChar ] > schwelle )
                    {
                        importantColumns.at( msaColCounter ) = 1; // unwichtig
                        cout << "... ... ... Schwellwert für " << currentChar << " getoppt, setze Spalte " << msaColCounter << " auf 1 \n";
                    }
                }
            }
            cout << "... currentSequenceString zeichenmäßig durchgegangen\n";
        }
        cout << "... alle Strings durch\n";
        cout << "main -  // flagImportantColumnsRelatedToIdentity()!\n";
    }

Irgendetwas mach ich aber mit der Map falsch, die Debug-Meldung sagt mir immer, dass eine neue Map angelegt wird, wenn ich in die zweite Zeile gehe. Es soll aber hier eigentlich die bereits bestehende Map für den ersten Spaltenstring genommen werden. Sieht jemand meinen Fehler ?

Mach mal ein paar Funktionen, bei dem ganzen Zeug kennt sich keiner aus. Oder soll das alles die Funktion sein die prüft, ob ein Zeichen zu oft vorkommt, dann ist sie viel zu kompliziert.

So sollte sie aussehen.

bool isKonserviert(std::string const& txt)
{
   //hier sollten max 10 Zeilen ausreichen
}

PS: Warum heißt das Konsverviertheit?

XSpille

Jay1980 schrieb:

Irgendetwas mach ich aber mit der Map falsch, die Debug-Meldung sagt mir immer, dass eine neue Map angelegt wird, wenn ich in die zweite Zeile gehe. Es soll aber hier eigentlich die bereits bestehende Map für den ersten Spaltenstring genommen werden. Sieht jemand meinen Fehler ?

Ohne deinen Code jetzt genau analysiert zu haben:

Überleg mal, was er in Zeile 41 macht

SoMapType currentMap;

Falls du es nicht siehst, kuck dir mal folgenden Code an:

#include <iostream>

class Foo{
public:
        Foo() : val(0) {std::cout << "Foo()" << std::endl;}
        ~Foo() {std::cout << "~Foo()" << std::endl;}
        int& value(){ return val;}
private:
        int val;
};

int main(){
        for(int i=0; i<3; i++){
                Foo foo;
                for(int j=0; j<3; j++){
                        std::cout << foo.value()++ << std::endl;
                }
        }
}

Foo()
0
1
2
~Foo()
Foo()
0
1
2
~Foo()
Foo()
0
1
2
~Foo()

Gruß,
XSpille

brotbernd

using namespace std;
	string text = "AAdfgABBCDHGFG;;:sdfgsfdg!$$%&§WDFGWdfgUJIJ";
	std::array<size_t, 256> counts = {0};
	for (auto it = text.begin(), end = text.end(); it != end; ++it)
		++counts[static_cast<unsigned char>(*it)];

	cout << *max_element(counts.begin(), counts.end()) <<
		" / " << text.size();

krümelkacker

Ich kann zwar mit dem Begriff "Konserviertheit" nichts anfangen, aber wenn es darum geht, zu gucken, wie oft der häufigste Buchstabe auftritt, könnte man den String auch einfach sortieren, einmal durchlaufen und sich merken, wie groß die größte gruppe von gleichen Buchstaben war.

int maxfreq(string s)
{
  int len = s.size();
  if (!len) return 0;
  sort(s.begin(),s.end());
  char z = s[0];
  int counter = 1;
  int max_counter = 1;
  for (int i=1; i<len; ++i) {
    char t = s[i];
    if (z==t) {
      ++counter;
    } else {
      max_counter = max(counter,max_counter);
      counter = 1;
      z = t;
    }
  }
  max_counter = max(counter,max_counter);
  return max_counter;
}

(einfach so runtergetippt ohne zu testen)

Mal auf brotbernds Idee aufgesetzt:

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <numeric>
#include <string>

class counter {
public:
  counter() { std::fill(counters_, counters_ + 256, 0); }
  std::size_t operator()(std::size_t n, char c) {
    return std::max(n, ++counters_[static_cast<unsigned char>(c)]);
  }
private:
  std::size_t counters_[256];
};

int main() {
  std::string text = "AAdfgABBCDHGFG;;:sdfgsfdg!$$%&§WDFGWdfgUJIJ"; 
  std::size_t n = std::accumulate(text.begin(), text.end(), 0, counter());

  std::cout << n << " / " << text.size() << std::endl;
}

Michael E.

krümelkacker: Warum lineare Laufzeit gegen O(n*logn) eintauschen?