<p>A key technology for sperm whale (<i>Physeter macrocephalus</i>) monitoring is the identification of sperm whale communication signals, known as <i>codas</i>. In this paper we present the first automatic coda detector and annotator. The main innovation in our detector is graph-based clustering, which utilizes the expected similarity between the clicks that make up the coda. Results show detection and accurate annotation at low signal-to-noise ratios, separation between codas and echolocation clicks, and discrimination between codas from simultaneously emitting whales. Using this automatic annotator, insights into the characterization of sperm whale communication are presented. The results include new types of coda signals, analysis of the distribution of coda types among different whales and for different years, and evidence for synchronization between communicating whales in terms of coda type and coda transmission time. These results indicate a high degree of complexity in the communication system of this cetacean species. Source code and data for our system is publicly available</p>