Wie vergleiche ich schnell Bitstrings variabler Länge in C++?

Question

Ich führe Vergleiche von Objekten auf der Grundlage des binären Vorhandenseins oder Fehlens einer Reihe von Merkmalen durch. Diese Merkmale können durch eine Bitfolge dargestellt werden, etwa so:

10011

Dieser Bitstring hat das erste, vierte und fünfte Merkmal.

Ich versuche, die Ähnlichkeit eines Paares von Bitstrings als die Anzahl der gemeinsamen Merkmale zu berechnen. Für einen gegebenen Satz von Bitstrings weiß ich, dass sie alle die gleiche Länge haben werden, aber ich weiß zur Kompilierzeit nicht, was diese Länge sein wird.

Diese beiden Zeichenfolgen haben zum Beispiel zwei Merkmale gemeinsam, also möchte ich, dass die Ähnlichkeitsfunktion 2 zurückgibt:

s(10011,10010) = 2

Wie kann ich Bit-Strings in C++ effizient darstellen und vergleichen?

Answer 1

Sie können die std::bitset STL-Klasse.

Sie können aus Bitstrings gebildet und UND-verknüpft werden und zählen die Anzahl der 1:

#include <string>
#include <bitset>

int main()
{
  std::bitset<5> option1(std::string("10011")), option2(std::string("10010"));
  std::bitset<5> and_bit = option1 & option2; //bitset will have 1s only on common options
  size_t s = and_bit.count ();                //return the number of 1 in the bitfield
  return 0;
}

EDIT

Wenn die Anzahl der Bits zur Kompilierungszeit nicht bekannt ist, können Sie boost::dynamic_bitset<> :

boost::dynamic_bitset<> option(bit_string);

Andere Teile des Beispiels ändern sich nicht, da boost::dynamic_bitset<> haben eine gemeinsame Schnittstelle mit std::bitset .

Answer 2

Schnellerer Algorithmus:

int similarity(unsigned int a, unsigned int b)
{
   unsigned int r = a & b;
   r = ( r & 0x55555555 ) + ((r >> 1) & 0x55555555 );
   r = ( r & 0x33333333 ) + ((r >> 2) & 0x33333333 );
   r = ( r & 0x0f0f0f0f ) + ((r >> 4) & 0x0f0f0f0f );
   r = ( r & 0x00ff00ff ) + ((r >> 8) & 0x00ff00ff );
   r = ( r & 0x0000ffff ) + ((r >>16) & 0x0000ffff );
   return r;
}

int main() {
        unsigned int a = 19 ;//10011
        unsigned int b = 18 ;//10010
        cout << similarity(a,b) << endl; 
        return 0;
}

Ausgabe:

2

Demonstration bei ideone : http://www.ideone.com/bE4qb

Answer 3

Da man die Bitlänge zur Kompilierzeit nicht kennt, kann man mit boost::dynamic_bitset anstelle von std::bitset .

Sie können dann operator& (oder &= ), um die gemeinsamen Bits zu finden, und zählen Sie sie mit boost::dynamic_bitset::count() .

Die Leistung ist abhängig. Um die maximale Geschwindigkeit zu erreichen, müssen Sie je nach Compiler die Schleife selbst implementieren, z.B. mit der Methode von @Nawaz, oder etwas aus Bit Twiddling Hacks oder durch Schreiben der Schleife unter Verwendung von Assembler/Compiler-Intrinsics für sse/popcount/etc.

Beachten Sie, dass zumindest llvm, gcc und icc viele Muster dieser Art erkennen und die Sache für Sie optimieren, also profilieren/überprüfen Sie den generierten Code, bevor Sie manuell arbeiten.

Answer 4

Verwenden Sie eine std::bitset Wenn die Menge der Merkmale kleiner ist als die Anzahl der Bits in einem Long (ich glaube, es ist ein Long), können Sie eine vorzeichenlose Long-Darstellung der Bits erhalten, dann et die beiden Werte, und verwenden Sie Bit-Twidling-Tricks aus aquí zu zählen.

---

Wenn Sie weiterhin Zeichenketten verwenden möchten, um Ihr Bitmuster darzustellen, könnten Sie etwas wie das Folgende tun, indem Sie die zip_iterator von boost.

#include <iostream>
#include <string>
#include <algorithm>

#include <boost/tuple/tuple.hpp>
#include <boost/iterator/zip_iterator.hpp>

struct check_is_set :
  public std::unary_function<const boost::tuple<char const&, char const&>&, bool>
{
  bool operator()(const boost::tuple<char const&, char const&>& t) const
  {
    const char& cv1 = boost::get<0>(t);
    const char& cv2 = boost::get<1>(t);
    return cv1 == char('1') && cv1 == cv2;
  }
};

size_t count_same(std::string const& opt1, std::string const& opt2)
{
  std::string::const_iterator beg1 = opt1.begin();
  std::string::const_iterator beg2 = opt2.begin();

  // need the same number of items for end (this really is daft, you get a runtime
  // error if the sizes are different otherwise!! I think it's a bug in the
  // zip_iterator implementation...)
  size_t end_s = std::min(opt1.size(), opt2.size());
  std::string::const_iterator end1 = opt1.begin() + end_s;
  std::string::const_iterator end2 = opt2.begin() + end_s;

  return std::count_if(
  boost::make_zip_iterator(
    boost::make_tuple(beg1, beg2)
    ),
  boost::make_zip_iterator(
    boost::make_tuple(end1, end2)
    ),
    check_is_set()
  );
}

int main(void)
{
  std::string opt1("1010111");
  std::string opt2("001101");

  std::cout << "same: " << count_same(opt1, opt2) << std::endl;

  return 0;
}