Original-URL des Artikels: https://www.golem.de/1003/73830.html    Veröffentlicht: 15.03.2010 10:19    Kurz-URL: https://glm.io/73830

Google gibt Bibliothek zur effizienten Suche frei

C++-Bibliothek RE2 sucht zeitlich linear nach regulären Ausdrücken

Google hat die C++-Bibliothek RE2 zur schnellen Suche nach regulären Ausdrücken unter der BSD-Lizenz freigegeben. Die Bibliothek findet bei Google vor allem bei der Suche im Onlinedienst Code Search Labs sowie bei der Suche über verteilte Daten mit Sawzall und Bigtable Verwendung.

Mit der C++-Bibliothek RE2 wird, anders als bei herkömmlichen Implementierungen, zeitlich nicht exponentiell in einer wachsenden Menge anhand von regulären Ausdrücken gesucht, sondern strikt linear. Dabei kommt die Automatentheorie zur Anwendung. Damit soll vermieden werden, dass pathologische Suchanfragen die Suchzeit unnötig in die Höhe treiben und dabei Ressourcen belegen.

Zudem wurde bei RE2 der Speicher, den einzelne Stacks belegen, begrenzt. Die Begrenzung verhindert nicht nur Stack-Überläufe und somit potenzielle Serverabstürze, sondern ermöglicht auch die Verwendung von RE2 in Multithread-Anwendungen. Weitere Details zu der RE2-Bibliothek liegen auf der Webseite des Projekts zur Einsicht. Dort liegt auch der Quellcode zum Download bereit.  (jt)


Verwandte Artikel:
Erste Vorschau auf Qt 4.6.0   
(09.09.2009, https://glm.io/69702 )
Tensorflow: Das US-Militär nutzt KI-Systeme von Google   
(07.03.2018, https://glm.io/133194 )
Google: Chrome wird künftig mit Clang statt Visual C++ entwickelt   
(06.03.2018, https://glm.io/133171 )
FTTH: Google Fiber hat seine Vision verloren   
(05.03.2018, https://glm.io/133146 )
Smarte Lautsprecher: Alexa ist beliebter als Google Assistant   
(05.03.2018, https://glm.io/133135 )

© 1997–2019 Golem.de, https://www.golem.de/